Es ist einfach zu entscheiden, ob ein Nash-Gleichgewicht besteht (es ist immer so); Es wird jedoch angenommen, dass es schwierig ist, eine zu finden (PPAD-Complete).
Was sind andere Beispiele für Probleme, bei denen die Entscheidungsversion einfach, die Suchversion jedoch relativ schwierig ist (im Vergleich zur Entscheidungsversion)?
Ich würde mich besonders für Probleme interessieren, bei denen die Entscheidungsversion nicht trival ist (im Gegensatz zum Nash-Gleichgewicht).
cc.complexity-theory
big-list
Travis Service
quelle
quelle
Antworten:
Hat eine gegebene ganze Zahl einen nicht-trivialen Faktor? -> Nicht trivial in P.
Finden Sie bei einer gegebenen Ganzzahl einen nicht-trivialen Faktor, falls es einen gibt -> Nicht bekannt, dass er in FP enthalten ist.
quelle
Hier ist ein weiteres Beispiel: Wenn ein kubischer Graph G und ein Hamilton-Zyklus H in G gegeben sind, finden Sie in G einen anderen Hamilton-Zyklus. Ein solcher Zyklus existiert (nach dem Satz von Smith), aber meines Wissens ist offen, ob es möglich ist berechnet in polynomialer Zeit.
quelle
Wenn Sie dem Folgenden den gleichen "Spielraum" geben, den Sie für Nash-Gleichgewichte tun, dann:
Es ist denkbar, dass hier eine Reihe von Gitterproblemen mit der gleichen großzügigen Zulage zur Definition des Entscheidungsproblems zusammenpassen:
Dies sind natürlich alle Fälle, in denen die von mir erwähnte Entscheidungsversion nicht sehr interessant ist (weil es trivial ist). Ein nicht ganz so einfaches Problem :
Das Entscheidungsproblem der planaren Graph-4-Färbbarkeit liegt in P. Die lexikografisch erste Lösung dieser Art ist jedoch NP-hart ( Khuller / Vazirani ).
Beachten Sie, dass die Eigenschaft, an der Sie wirklich interessiert sind, die Selbstreduzierbarkeit (oder besser gesagt die Nicht-Selbstreduzierbarkeit) ist. Bei dem Problem der planaren Graphfärbung besteht das wesentliche Problem darin, dass die Methode der Selbstreduzierung des allgemeinen Falls der Färbbarkeit die Planarität in einem Graphen zerstört.k
quelle
Lassen , der Zufall Graph auf 1 , ... , n , wobei jeder Rand mit einer Wahrscheinlichkeit unabhängig vorhanden ist 1 / 2 . Wählen n 1 / 3 Eckpunkten G gleichmäßig zufällig und fügen alle Kanten zwischen ihnen; rufen Sie das resultierende Graph H . Dann H hat eine Clique der Größe n 1 / 3 .G=G(n,1/2) 1,…,n 1/2 n1/3 G H H n1/3
Suchproblem: Finden Sie eine Clique mit einer Größe von mindestens .10logn
quelle
One more example; The Subset-sums equality: Givena1,a2,a3,...,,an natural numbers with ∑n1ai<2n−1 . The pigeon-hole principle guarantees the existence of two subsets I,J in 1,2,...,n such that ∑i∈Iai=∑j∈Jaj (since the are more subsets than possible sums). The existence of polynomial time algorithm for finding sets I and J is a famous open problem.
Subset-sums equality (pigeonhole version)
quelle
Another number theory example, similar to the ones above. It's known by Bertrand's postulate that for every positive integern , there's a prime between n and 2n . But we have no polynomial time algorithm currently to find such a prime, given n . (The desired algorithm must run in polylog(n ) time.) One can easily come up with polynomial time randomized algorithms because of the prime number theorem, and one can derandomize them by assuming some standard number theoretic conjectures (such as Cramer's conjecture), but no unconditionally polynomial time deterministic algorithm is known. Related work was recently done in the Polymath4 project; Tao's blog post on the project is a good summary of it.
quelle
At the risk of being slightly off-topic, let me give a simple and natural example of a theory C answer: Eulerian cycles and distributed algorithms.
The decision problem is not completely trivial, in the sense that there are are both Eulerian and non-Eulerian graphs.
There is, however, a fast and simple distributed algorithm that solves the decision problem (in the sense that for yes-instances all nodes output "1" and for no-instances at least one node outputs "0"): each node just checks the parity of its own degree and outputs 0 or 1 accordingly.
But if you would like to find a Eulerian cycle (in the sense that each node outputs the structure of the cycle in its own neighbourhood), then we need essentially global information on the graph. It shouldn't be hard to come up with a pair of examples that shows that the problem requiresΩ(n) communication rounds; on the other hand, O(n) rounds is enough to solve any problem (assuming unique IDs).
In summary:O(1) -time decision problem, Θ(n) -time search problem, and this is the worst possible gap.
Edit: This implicitly assumes that the graph is connected (or, equivalently, that we want to find an Eulerian cycle in each connected component).
quelle
Finding Tverberg partitions is of unknown complexity:
Like with Nash equilibria, the partition is guaranteed by the theorem, but it's not known if a polytime algorithm exists to find one.
Gil Kalai wrote a wonderful series of posts on this topic: One, Two and Three.
quelle
In all the examples above the decision problem is in P and the search problem is not known to be in P but not known to be NP-hard either. I want to point out that it is possible to have an NP-hard search problem whose decision version is easy.
Consider the generalized satisfiability problem for given relationsR1,…,Rk over Boolean domain {0,1} . An instance is an expression of the form
It was shown by Reith and Vollmer here that there exists a choice of relationsR1,…,Rk that make this problem NP-hard (actually OptP-complete) but keep the satisfiability problem easy (quite trivial actually). An example given in the paper is R={(1,0,0),(0,1,0),(1,1,1)} (here k=1 ). Once the satisfiability problem is solvable in polynomial-time, the question whether there exists a lexicographically minimal satisfying assignment is trivial.
See Corollary 13 and the example following it in the paper above (at least in this on-line version).
quelle
quelle
Take a "pairing-friendly" elliptic curve. That is, a curve that has a one bilinear mape associated with it - with e(a+b,c+d)=e(ac)e(ad)e(bc)e(bd) such that e is difficult to invert).
Such pairings are used widely in cryptography, partially since givene , it is trivial to solve Decisional Diffie-Hellman (given (g,h,ga,hb) , decide if a=b : just verify whether e(g,hb)=e(h,ga) ). However, it is still conjectured that the search/computational Diffie-Hellman problem is difficult.
Such groups are also generalized to "gap groups".
quelle
I guess Planar Perfect Matching got missed out from this list.
quelle
Let's notch up the complexity a bit.
Many decision problems about vector addition systems (VAS) are EXPSPACE-complete, but may require much larger witnesses. For instance, deciding whether the language of a VAS is regular is EXPSPACE-complete (e.g. Blockelet & Schmitz, 2011), but the smallest equivalent finite-state automaton might be of Ackermannian size (Valk & Vidal-Naquet, 1981). The explanation behind this huge gap is that there exist much smaller witnesses of non-regularity.
quelle