4
$\begingroup$

Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis?

$\endgroup$
  • $\begingroup$ A related question. $\endgroup$ – Juho May 21 '14 at 16:02
  • 1
    $\begingroup$ @Michael It could be EXPTIME problem. $\endgroup$ – Ari May 21 '14 at 16:19
  • 3
    $\begingroup$ @Michael All you're saying is that we don't know how to prove that problems in NP (or, more generally, PSPACE) aren't in P. For any complexity class X that includes EXPTIME, we know that any X-complete problem isn't in P by the time hierarchy theorem. $\endgroup$ – David Richerby May 21 '14 at 16:59
  • 1
    $\begingroup$ there are many problems studied in theory that are not in NP. although that might make another good question whether any are "encountered in practice". $\endgroup$ – vzn May 22 '14 at 5:21
  • 1
    $\begingroup$ @Michael I recommend you read some material about verification. They are very happy about double-exponential algorithms. In fact, often about deciders at all! $\endgroup$ – Raphael May 22 '14 at 7:30
14
$\begingroup$

The most common technique is to prove that the problem is hard for some class. For example, consider the problem HALT in which we are given a Turing machine $T$ and a number $n$ (encoded in binary, i.e., in the usual way), and the task is to decide whether $T$ halts within $n$ steps. HALT is EXPTIME-hard. If HALT were in P then P=EXPTIME (using the EXPTIME-hardness of HALT), which contradicts the time hierarchy theorem. We conclude that HALT is not in P.

Consider now a different problem, REGEXP-INT, in which given a list of regular expressions, we have to decide whether their intersection is empty. This problem is coPSPACE-hard, and so if it were in P, then P=PSPACE. While we don't know for sure that P is different from PSPACE, this is widely conjectured (and follows from P$\neq$NP), and assuming that, we conclude that REGEXP-INT is not in P. We call this a conditional result. Similarly, SAT is NP-hard, and so unless P=NP, SAT is not in P.

The unconditional results invariably use one of the hierarchy theorems, and so eventually, diagonalization. This technique itself cannot separate P from NP, due to the so-called "relativization" barrier (though non-black-box diagonalization still stands a chance).

$\endgroup$
5
$\begingroup$

The generally easiest solution for this kind of thing is to assume that you can do it, and show that it contradicts a well-established result.

The easiest case will be when you can show that the problem is undecidable -- not in P, not in NP, not guaranteed to halt, ever. Those solutions typically read like:

"Suppose, for contradiction, that there exists an algorithm for the Foo problem. I will show you that if I was able to solve the Foo problem at all, then I would be able to decide if any arbitrary program halted, since I can somehow reduce the question of "Does algorithm Bar halt on input $s$?" to an instance of the Foo problem. The halting problem is undecidable, a contradiction. Hence no such algorithm exists, in particular, no algorithm in P."

Your next best bet would be to show that it would give you a polynomial time solution to something in EXPTIME, and P $\subsetneq$ EXPTIME. That would look like this:

"Suppose, for contradiction, that there exists an $O(n^c)$-time algorithm for the Foo problem, where $c$ is a constant. I will show you that, in no more than polynomial time, I can reduce some existing problem known to be in EXPTIME but not in P to an instance of the Foo problem, a contradiction. Hence no such algorithm exists."

Anything other than that is hard. We haven't proved very many results about the limits of P.

$\endgroup$
  • $\begingroup$ @DavidRicherby the question was to prove that something was not in P, specifically, so I think that "Assume this is in P..." would be the most logical place to start. Beginning with that assumption yields you the conclusion "...a contradiction, therefore it is not in P" at the end, rather than "...a contradiction, therefore it is undecidable," which was not what Ari requested. $\endgroup$ – Patrick Collins May 22 '14 at 10:09
  • $\begingroup$ You're right, that's better. I edited my answer to reflect your comment. $\endgroup$ – Patrick Collins May 22 '14 at 15:30
4
$\begingroup$

Showing a lower bound on a problem is much harder than showing an upper bound. For an upper bound you simply must show an example algorithm of that complexity (a witness). Conversely, for the lower bound you have show that for all solutions each takes at least $\Omega(f(N))$ steps where $f(N)$ is some super-polynomial function. One simple case is where the output is exponential in the input.

  • The Towers of Hanoi is an example problem where one can prove a lower bound (of exponential time) in any solution. The gist of the proof is to show that any algorithm must generate each of the $\Omega(2^N)$ positions.

Another example (but one in $P$).

$\endgroup$
  • 2
    $\begingroup$ You want $\Omega(2^N)$? $\endgroup$ – Raphael May 22 '14 at 7:33
1
$\begingroup$

of course the big open question is P=?NP as commenters have noticed but you dont specifically mention NP. what neophytes not realize is that there are many problems proven outside of P, its just than none are NP-complete. it is possible to prove a problem takes more than P time ie is "not in P" if it takes eg ExpTime. the simplest way to prove a problem requires ExpTime is to prove it requires ExpSpace. this has been done with a sophisticated problem involving regular languages:

the proof involves showing that any TM that computes a language using Expspace can be computed by the above problem/formulation. so proving that any problem reduces to this ExpSpace complete problem in the above paper is sufficient.

$\endgroup$
  • 1
    $\begingroup$ Normally, the simplest way to show that a problem requires exponential time is to reduce an EXPTIME-complete problem to it. You'd expect proving an exponential space lower bound to be harder than proving an exponential time lower bound, since it's a stronger result. $\endgroup$ – David Richerby May 22 '14 at 2:39
  • $\begingroup$ DR all true yet—all known ExpTime-hard problems are ExpSpace-hard. a problem that is ExpTime-hard but not ExpSpace-hard would be a massive theoretical breakthrough & probably lead to major new class separations. eg P=?L seems to be closely related. $\endgroup$ – vzn May 22 '14 at 5:11
  • 3
    $\begingroup$ Quite the opposite! No EXPTIME-complete problem is known to be EXPSPACE-hard. If any were, this would imply that EXPTIME=EXPSPACE, which is expected to be false for the same reasons that P=PSPACE is expected to be false. $\endgroup$ – David Richerby May 22 '14 at 9:06
  • 2
    $\begingroup$ To add to this side-discussion, it is worthwhile to note that APSPACE=EXPTIME is known. So an alternating machine that has both non-deterministic and universal branching would actually only need polynomial space for exponential-time problems. Too bad my local computer vendor doesn't have alternating Turing machines in stock.... $\endgroup$ – DCTLib May 22 '14 at 12:59
  • 1
    $\begingroup$ @Ruedi Did you look on the internet? Amazon has everything, these days. $\endgroup$ – David Richerby May 22 '14 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.