Algorithms and Data 20: Harder Than
NP-Complete Professor Kevin Gold
•
NP-Complete problems are famously difficult and already hard enough — after all, no polynomial-time algorithms exist to solve them exactly
NP-Complete Is Not
As Hard As It Gets
Nevertheless, they are at least required to be in NP — Some problems are so hard, there’s not even an
•
checkable in polynomial time.
•
efficient way to tell a solution is correct.
And some problems are so hard, there can never be
•
any algorithm to solve them in any amount of time!
•
PSPACE
PSPACE is the class of all decision problems that are solvable in
•
polynomial space.
You can spend however long you like, but you can only use a
•
polynomial amount of memory.
Every problem that takes only polynomial time must also take
•
polynomial space.
We can’t allocate exponential amounts of memory in polynomial time, assuming there’s a constant maximum on memory allocated per operation
We could restate the above observation as P ⊆ PSPACE.
•
•
•
3-SAT is in PSPACE To solve a 3-SAT problem in polynomial space:
For every setting of variables to T or F,
Determine whether at least one literal in each clause is satisfied
•
by this assignment.
This doesn’t really take more space than recording the current variable
•
settings (linear in the number of variables) and the formula.
It takes exponential time, of course, but that’s not our concern for
•
showing something is in PSPACE
x1 = F x2 = F x3 = F
satisfied not satsified satisfied
(¬x1 v x2 v x1) ^ (x1 v x2 v x3) ^ (¬x3 v x2 v x1)
•
All Problems in NP Are In PSPACE
A polynomial-time reduction can’t take more than a polynomial amount of space (not enough time to allocate exponential memory)
So in polynomial space, we can reduce any
•
problem in NP to SAT, and then to 3-SAT
And then solve in a polynomial amount of space
•
using the method we just described.
•
Easy Problems
Are Also In PSPACE
Of course, simple problems like arithmetic also
•
take a polynomial amount of space.
All polynomial time problems are in PSPACE.
So being in PSPACE doesn’t necessary mean a problem is difficult, any more than being in NP means a problem is difficult.
•
But there are some hard problems in PSPACE, and
•
the most difficult of these are PSPACE-complete
PSPACE-completeness PSPACE-completeness is defined very similarly to NP-completeness.
A problem must be in PSPACE.
It is “PSPACE-Hard”
If any PSPACE-complete problem is solved in polynomial time, P = PSPACE! Think about the requirements for being NP-complete.
What would need to be true for a PSPACE-complete problem to also be NP-complete? Which requirement is clearly met, and which is not so clear?
•
•
• •
•
Every problem in PSPACE must be reducible in polynomial time to the
•
problem.
•
•
If a PSPACE-complete problem were solved in polynomial time, then every problem that could be solved in polynomial space could be solved in polynomial time.
This would be an even stranger world than P = NP.
•
P = PSPACE:
Not likely!
Most things we think of as having exponential
•
possibilities would be somehow polynomial time
•
It only takes n bits to represent 2n states, yet somehow we’d always be guaranteed to only need to explore polynomially many of those possibilities
•
•
This is determining the truth of a Boolean formula that uses the quantifiers
•
•
•
“for all x, there exists y such that (x or y) and (x or not y)” This one’s false: the formula is true for x = T but not x = F
For example, ∀x ∃ y [(x v y) ^ (x v ¬y)]
QSAT
Our first PSPACE-complete problem is what our textbook calls “QSAT” for
•
“Quantified SAT”
Also called TQBF, “True fully Quantified Boolean Formula” ∀ (for all) and ∃ (there exists) to quantify each variable.
A clear generalization of SAT … normal SAT is the special case of an ∃
•
quantifier for every variable
QSAT is PSPACE-Complete
Showing QSAT in PSPACE is straightforward: for each possible setting of the variables, check the formula for satisfaction.
•
The proof of its being “PSPACE-Hard” goes beyond
•
what will be covered in this class
•
It’s similar in flavor to the proof of SAT being
NP-Hard: deep down, deciding whether a program returns YES or NO can be thought of as a giant logic problem
QSAT and Games
A “winning strategy” for a game is a complete set of decisions
•
that will lead to victory regardless of the other player’s moves
•
•
In a two-move game, you have a winning strategy if there exists some move such that for all your opponent’s moves, you win anyway
In longer games, you have a winning strategy if there exists a move such that for all your opponent’s moves, there exists some move such that for all your opponents’ moves, there exists some move … etc etc … such that you must win
In other words, finding a winning strategy is solving QSAT
•
Generalized Geography
“Geography” is a game where players take turns calling cities — each city must begin with the letter the last ended with — can’t name one, you lose
Boston, Nantucket, Tallahassee…
“Generalized geography” is just taking turns choosing adjacent nodes on a graph without repetition (no legal plays = you lose)
•
•
•
Boston
Nantucket
Tallahassee
Naples
Generalized Geography is PSPACE-Complete
Runs in PSPACE: Recursively evaluate the game
•
tree at each level for a winning strategy
Space required is just the size of the stack of
•
moves
PSPACE-Complete because there is a polynomial
•
time construction to solve QSAT
Sketch of the QSAT-Solving GG Construction
Assume WLOG the formula alternates between ∃
•
and ∀ variables (can insert dummy variables)
Create this graph:
∃ player gets to pick literal —
if satsified, no legal move for ∀
•
true
false
and ∃ wins, else ∀ wins
∀ player gets to
pick clause – unsatisfied means ∀ wins
∃ x1 (p1 picks)
∀ x2 (p2 picks)
x1 x2 x3
c1
c2
(coming back from var assignment)
…
x1
Two Other
PSPACE-Complete* Games
Hex Othello *For n x n generalizations of the board
•
•
•
Planning
Suppose an Artificial Intelligence (AI) wants to achieve some state of the world that requires a plan with multiple steps
Solve a sliding block puzzle
Do a grocery run: drive to gas station, get gas, go to store…
A classic AI represents the whole world in terms of logical statements about it. We can treat these as Boolean variables here.
15inSquare15 = TRUE, PuzzleSolved = FALSE
HaveGas = FALSE, HaveBread = FALSE
•
• •
The AI has some actions it can perform that require some states of the
•
world to be true or false, and then cause some states to be true or false
Preconditions, Postconditions, and World States
An Planning Problem action has some preconditions postconditions that are true after the action is taken
•
that must be true in order to take the action and
•
DriveToStore
Preconditions: HaveGas = TRUE, InCar = TRUE
Postconditions: AtStore = TRUE, AtHome = FALSE
Given some initial state of the world, the Planning Problem is to find a sequence of actions that drives the world state to some desired state
(HaveGroceries = TRUE)
•
There Are Planning Problems With Necessarily Exponential-Length Solutions
The binary counter problem:
Starting state — n bits.
Goal — Achieve all bits flipped to 1.
Action Flipi:
Precondition: All bits to the right of bit i == 1.
Postcondition: Set bit i to 1, set bits to the right of it to 0.
•
We can easily define a silly planning problem that must take an
•
exponential number of steps
In other words, the only legal action each step is to increment the binary
•
counter by 1.
This will take 2n – 1 steps, even though the problem description is O(n)
•
space.
If Planning Solutions are Exponentially Long, They Can’t Be Certificates for NP
This is a subtle point about NP: to be in NP, a
•
certificate has to be checkable in time polynomial in the
•
size of the problem description, not the certificate
If a certificate can be exponentially long — like the “binary counter” plan that would have 2n-1 steps — it is unacceptable as a proof of being in NP.
Students commonly mistake harder problems for certificate must be polynomially long in the input for NP
•
problems that are in NP because they forget the
Planning is in PSPACE
Despite the fact that the full solution is potentially exponentially
•
long, Planning can always be solved in polynomial space
At least to figure out whether there is a solution and what the Suppose there are N variables to be set to true or false. Then if
•
first move is.
•
there is a working plan, it need not take more than 2N steps.
Otherwise it would repeat a variable configuration; what
•
would be the point of that?
If we’re clever, we can at least decide whether such a plan
•
exists by being very frugal about space
Savitch’s Divide and Conquer Trick for Saving Space
// Given world states W1 and W2, check whether a
// plan with at most MaxSteps gets from W1 to W2
Decide-Plan(W1, W2, MaxSteps):
If MaxSteps == 1
Check whether any action can get from W1 to W2 in one move —
return YES if so, NO if not
n
For all possible intermediate world-states W’ // All 2 of them, ouch
StartToHalfway = Decide-Plan(W1, W’, MaxSteps/2)
HalfwayToFinish = Decide-Plan(W’, W2, MaxSteps/2)
If StartToHalfway && HalfwayToFinish
Return TRUE
Return FALSE
Don’t save the path, just YES or NO
This recurrence takes polynomial space p(n) per recursive call on the stack, and the stack goes log(MaxSteps) = log(2n) = n steps down. np(n) is still polynomial space — it’s just a lot of computation
• • •
• •
Planning is
PSPACE-complete
We can reduce from QSAT (proof omitted)
Artificial Intelligence as a field has always loved “impossible” problems
But as with NP-complete problems, not all particular instances of planning are hard
Students typically write 15-puzzle solvers in AI classes
Some problems have a structure that makes it easy to know what solutions would be best to try next — there may be good heuristics that allow short solutions to be found quickly
In the 15-puzzle case, “try solutions that reduce the distances
•
between tiles and their final destinations” is a good heuristic
•
•
EXPTIME is the class of decision problems that can be solved in exponential time (O(2p(n)) for some polynomial p(n)
If someone proved P = EXPTIME, then every problem solvable in exponential time could also be solvable in polynomial time.
EXPTIME and
EXPTIME-Complete
Unlike the other equalities I’ve mentioned, this has been
•
actually proven to be impossible.
Which means that if a problem is EXPTIME-complete, there
•
really is never going to be a polynomial time algorithm.
•
EXPTIME-Hard (handwavy): If we could figure out what programs will do at the end of exponential time in polynomial time, we could use our polytime analyzer program to solve all those hard problems without ever running the code.
An EXPTIME-Complete
Problem
“Time-limited halting problem”: Does this program stop within
•
k steps?
Possible in exponential time: Just run the program. (k is in
•
binary, so this takes exponential time)
For example, make the program halt only if the answer is
•
YES, then run our halting-analyzer on that
Some EXPTIME-Complete Games
Chess Checkers Go
In each case, the game is generalized to n x n, and the problem
•
is to figure out who wins with optimal play
This does not mean playing as well or better than the best
•
humans is impossible!
•
Even Harder Problems
There exist even harder solvable problems than the EXPTIME-complete problems, but they tend not to be very natural.
The next big category of difficult problems you should be
•
aware of are the undecidable or uncomputable problems.
•
•
These are problems that can’t be solved with any algorithm — usually because there’s some kind of paradox surrounding what we’re asking for.
You’ll see more about this in Theory of Computation.
•
This is because there’s a logical contradiction hidden in what we’re asking for: to make it work on any program, our program would have to work on itself and any program calling it as a subroutine.
The “Halting Problem” is
Impossible to Solve
It’s not possible to make an algorithm that takes an arbitrary
•
program and input and decides whether it will halt on that input.
In fact, most problems about analyzing what programs do are
•
impossible in the general case!
Basic idea: what if we programmed our program to analyze
•
itself and then do the opposite of what it’s “supposed” to do?
A Halting Program Argument
•
•
In other words, HALT?(P,I) is a logical impossibility.
Suppose we have a subroutine HALT?(P, I) that says YES if program P halts on input I
•
and NO otherwise.
Write the following program META-HALT?(P):
•
META-HALT?(P):
If HALT?(P,P)
While (true) {}
// Loop forever
Now run META-HALT on itself. Does it halt?
Else
Return YES
Suppose it does. Then HALT?(P,P) must have returned NO.
Suppose it doesn’t. Then HALT?(P,P) must have returned YES. That’s a mistake
•
So META-HALT isn’t supposed to halt on itself. Contradiction.
•
because we just said META-HALT? doesn’t halt on itself. Contradiction.
Lots of Program Analysis is Not Possible In the General Case
Questions of the form “Does this program ever do so-and-so?” or “Will this program compute this function correctly?” are not computable in the general case.
•
We can show that if we could answer those questions, we
•
could solve the Halting Problem (using reductions)
Of course, just as with Planning, there may be easy “instances”
•
of these unsolvable problems.
You can certainly look at the code “while (true) {}” and decide But no algorithm will work for all inputs.
•
it doesn’t halt. So could a program.
•
•
Summary: Even Harder than NP-Complete
PSPACE is the class of problems solvable in polynomial space, and solving a PSPACE-complete problem would mean every such problem could be solved in polynomial time. This is really unlikely!
If P = PSPACE, P = NP as a side effect
EXPTIME-Complete problems are definitely not going to be And some problems will never have algorithms at all!
NP-complete problems at least are guaranteed to be checkable
•
in polynomial time. Harder problems exist.
•
•
solved in polynomial time
•