New answers tagged

3

The result you are trying to prove is known as Mahaney's theorem. It is covered by textbooks on complexity theory, and in many online lecture notes. The proof in Jonathan Katz' lecture notes indeed uses LEXSAT.


1

There are a few issues to consider. If P!=NP, this approach is doomed from the start because you can't try every one of the infinite number of possible algorithms in finite time. That's I think the main deal-breaker here. Unless P=NP, which most people doubt, then the best you could ever do is say "my AI failed to find a polynomial-time algorithm in X ...


3

Here is a possible analog of the P vs NP question for straightedge-and-compass constructions. Suppose that we are given a line with three points $a,b,c$ on it, and consider the following question: Given just the line and the points $a,b$, can we construct the point $c$ using a straightedge and compass? If we are given a construction, then we can verify ...


1

First of all, P vs NP is about computability by Turing machines/computers and not about straightedge and compass constructions. Your "problem", as you suspect, does not really fit the definition of "problem" in the sense of P vs NP. A problem in the sense of P vs NP (formally called a "language") is simply a set of (binary) strings. So, if $\{0,1\}^*$ ...


Top 50 recent answers are included