On Trial: P versus NP and the Complexity of Complexity
BLOG: Heidelberg Laureate Forum
If I asked you to prove in a court of law whether sorting a long list of numbers in order from lowest to highest was as complex a task as, say, solving a massive Sudoku puzzle, you might think I had lost my marbles. You would certainly question why taxpayers’ money was being squandered on a trial about a frivolous topic.
Yet, there may be more merit to bringing the case to court than first impressions would suggest. The relative difficulty of tasks like these is the fundamental question underlying one of the most pernicious problems in mathematics and computer science that has remained unsolved since its formulation in 1971: the P versus NP problem. The solution to this problem has huge ramifications in the real world, impacting medicine, artificial intelligence, internet security and a host of other areas. For these reasons, P versus NP is one of seven Millenium Prize Problems selected by the Clay Mathematical Institute as the most important to solve in our time.
The Civil Case
The “P” of P versus NP stands for “polynomial time.” A computer program runs in polynomial time if, when you increase the size of the input, the (idealised version of a) computer takes a proportionately longer time to complete its given task. List-sorting is a perfect example of a P problem, where there are known and straightforward methods of sorting the list and verifying that the list is sorted correctly that don’t scale at some absurd rate as the length of the list increases.
Expanding the “NP” of P versus NP is less informative (for the record, it stands for “nondeterministic polynomial time”), but in essence, NP problems are hard to solve and easy to verify. A generalised version of Sudoku – where instead of having a 9 × 9 grid you allow the grid to be arbitrarily large (n2 x n2) – is an NP problem. There is no known way to solve it that is significantly faster than brute-force checking of every possible combination of numbers to fill the board. As a result, when you increase n, the time to solve the puzzle scales faster than exponentially; i.e. it gets really hard to solve, really quickly. However, verifying a solution remains polynomial in time, as you can run a relatively simple and quick algorithm to check that the digits entered in all rows, columns and squares follow all the rules; i.e. it remains easy to verify.
Relating what you now know about the P versus NP problem to list-sorting and taking on a massive Sudoku puzzle, the answer to the question of which is more difficult to solve seems even more obvious – list-sorting, hands-down! If you then applied the same train of thought to a large selection of P problems and NP problems and presented your findings in a civil court of law, it would be easy to show that – based on the balance of probabilities – all list-sorting-type problems are not equivalent to all massive Sudoku-like problems, i.e. P ≠ NP, and you would win your case easily.
The Criminal Case
But mathematicians and computer scientists require a higher standard of proof than that. In fact, society demands a higher standard of proof than that; because if P does turn out to equal NP, in principle, currently intractable problems will become easy. And this fact could be used for good – such as optimising transport routing and finding new medicines – or ill, including hacking bank accounts and government websites. Like juries in a criminal court determining the guilt of defendants, we all need to know beyond reasonable doubt whether or not P = NP. And that is a much tougher proposition.
Towards this aim, researchers have shown that nearly all seemingly hard NP problems are “NP-complete,” which means that if they had an efficient solution to one NP-complete problem, it could be adapted to solve every other NP problem quickly too. For example, generalised Sudoku is NP-complete, because it can be reduced to other classic complex problems that are known to be NP-complete, including the (clearly similar) Latin square completion problem and the (on the face of it, very dissimilar) Hamiltonian cycle problem. They are – in a precise mathematical sense – equivalent.
Therefore, to prove whether P does or does not equal NP, all a plucky researcher has to do is discover a clever algorithmic trick that solves an NP-complete problem in polynomial time (P = NP) or, alternatively, find just one NP-complete problem that they can prove is not solvable quickly by any computer program (P ≠ NP). However, despite half a century of effort from some of the brightest minds, proof – one way or another – remains elusive.
Complexity of Complex Problems
In recent years, many researchers have taken a step back from attempting to directly solve P versus NP. Instead, they have been questioning why solving P versus NP and similar problems is difficult in the first place. They have been asking questions such as “how hard is it to determine the difficulty of various computational problems?” and “why is it hard to determine how difficult they are?” These and other “meta” problems are the foundations for an area of mathematics and computer science called “meta-complexity”; both a topic of study and a tool that researchers are attempting to use in order to attack problems such as P versus NP.
An important focus for meta-complexity researchers at the moment is a particular problem with a long history that continues to defy clear classification: the minimum circuit size problem (MCSP). MCSP is interesting for several reasons, not least because it is one of the few challenging computational complexity problems left where it remains unclear whether it is NP-complete or not.
Found to play a central role in diverse areas such as cryptography, proof complexity, learning theory and circuit lower bounds, MCSP asks: Can you determine whether a black-box hypothetical computer used to compute a Boolean function has high or low circuit complexity? A Boolean function takes as input a certain number of zeros or ones and outputs zero or one (true or false). From this you can construct a truth table: a tabular representation of all the combinations of values for inputs and their corresponding outputs. Essentially, the truth table provides the input-output behaviour of the function, but gives no information about the function’s computational complexity. This complexity is represented by circuit complexity, defined as the total number of logic gates needed to build the smallest circuit that can compute the given function.
With these clarifications, the problem can be presented more precisely: MCSP takes as input the description of a Boolean function f as a truth table as well as a circuit size parameter s, and asks “is there a circuit that computes f of size ≤s?” As MCSP is both computationally complex and about computational complexity, it is unusual in being a meta-, meta-complexity problem, or a meta2-complexity problem. The fact that researchers are trying to figure out why it is hard to determine how difficult MCSP is to solve, means it could be argued to be even more meta; a meta3-complexity problem perhaps.
For the simplest Boolean functions, MCSP can be solved by an algorithm that runs in polynomial time. But the vast majority of functions seem to require an exponentially increasing number of gates as the functions get larger. Like generalised Sudoku, MCSP seems impossible to solve unless using a brute-force search, but also easy to verify if you are given a solution. You can guess a circuit, run every possible input and see if the output matches that of the given Boolean function. It is therefore clearly an NP problem. But is it also in P? Is it an NP-complete problem, i.e. would a fast way of solving it mean proving all problems in NP are actually in P? Many in the community suspect MCSP is not in P, but is NP-complete, which, if proven, would definitively mean that P ≠ NP.
Progress Towards a Resolution?
In recent years, researchers have made significant progress in showing MCSP is NP-complete. For example, a huge number of proofs, many in the past six years, have emerged showing variants of MCSP are NP-complete. Perhaps some of the most interesting progress has been made by Shuichi Hirahara from the National Institute of Informatics in Tokyo.
In 2018, Hirahara derived a worst-case to average-case reduction for MCSP. Here, “average-case” complexity is a gauge of how easy or hard a problem is on average for most inputs, whereas “worst-case” complexity is the standard approach, considering the maximum complexity of the problem over all possible inputs. Problems where average-case and worst-case complexity may differ are interesting, as they can provide insights into the foundational complexity of these problems. Hirahara’s result implies that a hypothetical average-case MCSP algorithm would actually be powerful enough to solve a slightly different version of MCSP that restricts the types of circuits allowed without making any mistakes. This result is exciting because no other NP-complete problem has a known worst-case to average-case reduction. Given all NP-complete problems’ equivalence, it therefore provides a new avenue for research into the P versus NP problem.
Next, in 2022, using a blend of complexity theory and advanced information theoretic cryptography, Hirahara proved that MCSP on partial Boolean functions is NP-hard (NP-hard problems are as hard as NP-complete problems but do not necessarily have to be in NP). A partial Boolean function has a truth table that contains the usual zeros and ones, but also some “don’t know” symbols – some could be either zero or one, where you do not care what the circuit does. Somehow, adding this “don’t know” ambiguity allows a host of useful techniques to be deployed to resolve the partial-MCSP problem, but so far, it is unclear whether these same techniques can be applied to resolve the original MCSP problem.
Another researcher, Rahul Ilango from Massachusetts Institute of Technology, has been working to prove MCSP’s NP-completeness in multiple ways, looking at both simpler and more complicated versions of MCSP as entry points from which to attack the main problem. His most recent meta-complexity result succeeds in linking MCSP with the seemingly disparate set of Boolean satisfiability problems (SATs), where you are given a representation of a Boolean function as a formula or circuit and asked information about its function (e.g. whether it has a one in its truth table, or if it outputs a certain pattern of zeros and ones, etc.).
MCSP is what is known as a “black box problem”, because you want to know something about the representation, given black box access. SATs are completely different. Known as “white box problems”, SATs aim to say something about a function, given its representation. In 2023, Ilango and colleagues made the startling discovery that SAT reduces to MCSP with a random oracle, i.e. with a perfectly random function computable in P and accessible to all circuits and computers. As SAT is well known to be NP-complete, MCSP with a random oracle must also be NP-complete.
These and other recent results add to the case that the original MCSP is in fact NP-complete too. And, if this is true, MCSP could hide the missing piece of evidence that proves beyond reasonable doubt whether P does or does not equal NP.
Much like the problem itself, the trial of P versus NP has certainly been complex and lengthy, but progress is being made, and it feels like researchers are finally inching closer to a verdict.
No, I think. It would mean P ≠ NP and P = NP at the same time.
Like philosopically thought, does the sun shine, if on your location is night? Or can we have shadow without light?
We are very used to think binary and that’s fully okay. But can we think a dimension above? What if we think ternary, keeping binary, but adding a view point that accepts both at the same time?
Just thinking … and yeah it is a … hell of a problem, thanks for reminding.
To reduce it to binary this would mean to find a term where
x = (P = NP) = (P ≠ NP)
is always true.
For me this is a problem where we have to leave our current expectations and thought limits. Like this drawing puzzle with 9 points to connect with a constant line. We must leave our box to get a glimpse of the possible solution.
Not always true, true in defined situations. Too stupid to find a way to edit the post.
Now just read the rest, I think Hirahara is on a good path. Break the puzzle into pieces you can manage and may it cost a new category.
About reducing to SATs, of course elegant, I’m not sure, but, who knows.
Nach meiner Meinung ist P versus NP nur mathematisch lösbar.
Am Beispiel von Sortierverfahren.
Hier ist klar, P ist ungleich NP, wenn man nur mit Dualzahlen rechnet.
Der Computer bzw. das Programm muss eine Schleife durchlaufen, wenn sie eine neue Zahl einsortieren muss.
Mit einem Quantencomputer kann man die Durchläufe verringern, weil die “Vergleiche” der Zahlen ob größer, kleiner oder gleich, “gleichzeitig” stattfinden können. Die Qubits beruhen nicht auf “on” oder “off” sondern auf der Verschränkung der Möglichkeiten.
Und da man die Möglichkeiten der Verschränkung nicht direkt sieht, sondern nur errechnen kann, ist die Aussage P gleich/ungleich NP nur ein sprachliches Problem, kein reales Problem mehr.
Nur meine Meinung!
Sehr lustig.
Was für Sie klar ist, da mühen sich andere so richtig ab. Ihre Begründung zeigt eigentlich nur, dass Sie gar nicht verstehen, um was es geht.
Eine sprachliche Erklärung zu P ungleich NP
P seine eine Menge P
NP sei die Summe der Teilmengen von P
dann gilt P ungleich NP
Wenn man die Teilmengen von P , also NP auf P verkürzt, dann gilt P gleich NP-
Bei der Fourieranalyse von Schwingungen wird das praktisch gemacht, jede Sinusschwingung kann in ihre Frequenzkomponenten zerlegt werden.
So ist die Sinusschwingung gleichzeitig die Summe ihrer Frequenzkomponenten.
Eigentlich banal.
Eine Tüte mit Äpfel ist gleichzeitig die Summe ihrer Äpfel.
Vielleicht sollte man bei gleich und ungleich auch noch den Begriff „identisch gleich“ einführen, allso das Gleichheitszeichen mit 3 Strichen. Identisch-Zeichen ( ≡ )
Dann könnte man als Kompromiss sagen : P = NP aber nicht P ≡ NP
@N(P?)
Sie scheinen Ihre Ansichten schnell zu wechseln, vergleiche:
Na gut, aber das ist wirklich genial:
Wenn man unter P und NP also etwas ganz anderes versteht als im Artikel beschrieben – und dann noch unter einer Summe von Mengen irgendetwas geheimnisvolles- dann lässt sich das Problem lösen.
Wunderbar!
@N(P)@all
Die Sache ist klar.
Die Lösung steht in einem Statistikbuch in einem tschechischen Antiquariat..
Flauschig
mit Tschechenbashing kommt man dem Problem nicht nahe.
Ob N ungleich NP sei, diese Scheinfrage wurde gestellt ,um eine übergordnete Sichtweise von Sortieralgorithmen zu finden. Hat leider bis heute niemand gefunden.
Herr Skuse ist nicht alt genug um das zu durchschauen.
Darum geht’s doch nicht.
Wie interessant!
Es geht wohl um die Frage,ob der Nick @N demnächst durch @NP ersetzt wird.
Schade um das Thema oben,das da lautete
P vs NP
Fluffy,
der blog hier glänzt mit wenig Beiträgen.
Das liegt daran, dass die Zielgruppe studierte Mathematiker sein müssen.
Ich bin kein studierter Mathematiker , mich interessiert das dennoch, und wenn du das merkst, dann wäre das eine edle Aufgabe für dich, das Problem anhand eines konkreten Beispieles aufzuzeigen.
Mir ist nicht klar, was Herr Skuse erwartet. Eine Lösung des Problemes?
ein neuer, genialer Zugang ?
Oder will er nur testen, ob so ein Thema für eine Fachzeitschrift genügend Aufmerksamkeit bekommt.
Schade um das Thema, das kann ich nur bestätigen.
@N
Das steht klar im Text. Es ist auch klar, dass Ihnen das nicht klar ist.
Klar ist auch, dass es für Sie völlig unverständlich bleiben wird, warum einige nur dann etwas sagen, wenn sie etwas zu sagen haben.
Joker,
das ist doch mal ein schöner Zirkelschluss.
“Klar ist auch, dass es für Sie völlig unverständlich bleiben wird, warum einige nur dann etwas sagen, wenn sie etwas zu sagen haben.”
Und …. es beschreibt den Kern des Problemes. Wenn man nichts zu sagen hat, dann sagt man nichts.
Und…..ich habe immer etwas zu sagen, und das ist doch das Wesen des Internets, eine Diskussion anleiern, damit alle profitieren.
“and it feels like researchers are finally inching closer to a verdict.”
So, so !
Auf jeden Fall, danke, dass du überhaupt geantwortet hast.
I am closer to an end.
Jetzt gehn wir mal analytisch heran !
Die Behauptung über Sudokus stimmt nicht.
“Es gibt keine bekannte Möglichkeit, es(ein sudoku mit beliebig großem Raster) zu lösen, die deutlich schneller ist als die Überprüfung jeder möglichen Kombination von Zahlen, um das Board zu füllen.
Die Zahlen in einem Sudoku sind nicht nur Zahlen, man kann sie auch mit Farben ersetzen und dann erkennt man in dem Sudoku ein Muster. Und dieses Muster wiederholt sich. Egal wie groß das Sudoku ist.
Über die Musterekennung sieht man sofort, dass es mit Mustererkennung schneller geht als mit dem Ausfüllen des Sudokus mit Zahlen.
Dann wäre NP sogar kleiner als P !
@N
Das scheint mir exakt zu beschreiben, was es beim Sudoku zu vermeiden gilt, was für eine Lösung gerade ausgeschlossen ist.
Eine kleine Hausaufgabe für Lehrer: Wie groß ist die maximale Größe n eines auf Farben basierenden Sudokus (n² x n²), das auf einem Monitor bei 48 Bit Farbtiefe noch dargestellt werden kann?
Korrektur
PN wäre dann keiner als N
@P (*)
Wollten Sie vielleicht sagen, IQ wäre dann kleiner als 0?
(*) P = N
@N
Nur mal für dein Verständnis.
Der Text enthält bis hierher 1228 N’s, 528 P’s und 93 NP’s, inklusive deiner Nicker N’s.
Folgt jetzt daraus N = P oder N ≠ NP oder sonst noch was?
Oh ich vergaß die PN’s.
Bis jetzt sind genau 3 PN’s enthalten.
Das ist ja fast eine Nullmenge.
Joker,
Das Sudoku ist nur ein Beispiel.
Es gibt zwei Arten von Sudokus. Die Symmetrischen und die mit gebrochener Symmetrie.
Bei den Symmetrischen sind die genaue Anzahl der Zahlen gleich.
Also ein 3×3 Sudoku hat 9 Zahlen und damit 81 Felder. Von jeder Zahl sind genau 9 vorhanden.
Warum willst du das ausschließen. Es geht ja hier um einen Ausfüllalgorithmus.
Und wenn das Muster erkannt ist, dann geht das Ausfüllen nach einer Regel und nicht mehr nach try and error.
Fluffy
komm mal aus dem Nebel heraus und sage, was bei Dir ein P ist und was ein N ist und was ein PN ist.
Nein, nein, nicht was es bei Fluffy ist, sondern für was es im Artikel steht wäre wichtig zu verstehen. Und das steht im Artikel:
Von N und PN ist im Artikel nicht die Rede. Klar, oder?
@N
Was möchte ich ausschließen?
Sicher möchte ich nicht ausschließen, dass in einem 9 x 9 Sudoko genau 9 Zahlen (9 Buchstaben oder 9 Farben) vorkommen, jede(r) 9 mal.
Im Gegenteil sogar, ich würde darauf bestehen.
Da würde mich dann doch mal interessieren was Sie hier unter ‘Muster’ verstehen und was unter ‘Regel’. – Ach nein, eigentlich doch nicht.
Joker
” Ach nein, eigentlich doch nicht.”
Kein Problem damit.
Letzte Erkenntnis: N = PN ist gar keine Gleichung. Jedenfalls weder eine physikalische noch eine mathematische.
Was Sie uns hier so als Erkenntnis verkaufen wollen.
Wie bereits gesgt, weder N noch PN tauchen im Artikel auf.
Joker
“NP, is a fundamental concept in computational theory and complexity science. It refers to a class of decision problems for which a “yes” solution can be verified by a deterministic Turing machine in polynomial time.”
Das soll doch heißen, dass das Programm Logikaufgaben in Abhängigkeit der Schleifendurchläufe lösen kann. Bei NP Aufgaben kann die Anzahl der Schleifendurchläufe nicht ermittelt werden.
Ich ahne jetzt, das ist eine ganz vertrackte Aufgabe .
Nein.
(Wikipedia ; Hervorhebung durch mich)
Nachtrag
es muss heißen “Kann die Anzahl der Schleifendurchläufen nicht vorher ermittelt werden.
@N
Für dich ist die Koch-Kurve vielleicht auch ein Problem aus der Küche.
Ist es noch ein Schnitzel,wenn
PNP = Panade-Nix-Panade ?
Joker,
Die Menge der Probleme, die schnell lösbar sind, die werden mit einem “Vorwärtsalgorithmus ” gelöst. Ich nehme mal an, damit meint man in polynomer Zeit.
Wenn man die Korrektheit überprüft, braucht man einen Rückwärtsalgorithmus, und der kann sehr viel längere Zeit in Anspruch nehmen, aber auch viel kürzer sein, wenn man ihn denn hat.
Ein einfaches Beispiel.
du hast eine sehr große Zahl, von der behauptet wird, sie sei eine Primzahl.
O.K. Du teilst also durch alle Zahlen von 2 bis P/2 . Das kann jetzt sehr lange dauern. Das wäre jetzt ein Rückwärtsalgoritmus,
und das sonderbare dabei , es gibt noch keinen Vorwärtsalgorithmus zum Auffinden von Primzahlen.
Damit ist das Problem gelöst,
Die Anzahl der Probleme die schnell auf Korrektheit überprüft (die Überprüfung auf prim)werden können ist gleich groß als die Probleme die schnell gelöst werden können.(das Auffinden von Primzahlen)
Bei den Primzahlen gilt N = NP.
Mein tipp: es hängt vom Problem ab, ob gilt N = NP.
Ob es jetzt mehr Probleme des N-Typ gibt oder den NP-Typ
oh je, jetzt muss man einengen.
Rekursive Algorithmen sind vom NP-Typ-
Von denen gibt es gefühlsmäßig weniger.
Soviel Blödsinn auf einem Haufen. Das wegzuschaffen, dieses Problem ist definiitv nicht schnell lösbar – wenn überhaupt.
Suche den Fehler.
Unsinn
Unsinn
Unsinn
Unsinn
Unsinn zum Quadrat
Unsinn
Unsinn hoch drei.
Polynomialer oder Exponentieller Unsinn?
😀😄😄
Joker,
Vorwärtsalgorithmen sind induktiv, Rückwärtsalgorithmen sind deduktiv.
Diese Ausdrücke kennst du doch?
Anmerkung : Alles auf “Unsinn” zu reduzieren ist auch ein Algorithmus.
Anmerkung: “Problem gelöst” ,das war ein kleiner Scherz zur Aufmunterung.
Fluffy
Unsinn ist meistens linear ! Wäre er exponentiell könntest du ihn gar nicht mehr als solchen erkennen.
Es wäre wünschenswert, mal ein praktisches Beispiel von Dir zu hören.
Mach doch wenigsten einen Witz über “Unsinn”.
Sie scheitern doch schon an einzelnen Buchstaben.Bei Ausdrücken ist es noch schlimmer. Sie sind es, der die immer wieder, wie auch hier, in offensichtlich unsinniger Weise zu einem bedeutungslosen Brei zusammenrührt.
Vielleicht überlegen Sie es sich ja und gehen nochmal in die Schule – aber nicht als Lehrer.
Joker,
das war wieder eine astreine Projection.
Da gehe ich doch lieber Kuchenbacken.
Previously available exclusively at Stop & Shop, Nature’s Promise private-label products are now offered at Hannaford as well. The Federal Trade Commission mandated that 10 Hannaford locations be sold to other retailers in order for the merger to proceed.
Talktohannaford.comhttps://talktohannafordcom.info/