Complexity

Question 1

P

Answer 1

P is the class of decision problems that can be solved by a computer in polynomial time,

Question 1

P vs NP

Answer 1

whether every problem that can be quickly checked for a solution can also be quickly solved by a computer.

Question 2

NP

Answer 2

NP is the class of decision problems for which a proposed solution can be verified quickly by a computer in polynomial time.

Question 3

NP-Hard

Answer 3

A problem is NP-hard if every problem in NP can be reduced to it by a polynomial-time reduction.

Question 4

NP-Complete

Answer 4

A problem is NP-complete if it is both NP and NP-hard.

NP-complete problems are the hardest problems within NP.
If you could solve any one NP-complete problem quickly, you could solve every problem in NP quickly.

Question 5

coNP

Answer 5

coNP is the class of decision problems whose complements are in NP.

Question 6

PSPACE

Answer 6

PSPACE is the class of decision problems that can be solved using polynomial space, where the amount of memory used grows at most as a polynomial function of the size of the input.

Question 7

CLIQUE

Answer 7

The CLIQUE problem asks whether a graph contains a complete subgraph of a certain size.

Question 8

L

Answer 8

L is the class of decision problems that can be solved by a computer using logarithmic space, where the amount of memory used grows logarithmically with the size of the input.

Question 9

NL

Answer 9

NL is the class of decision problems for which a proposed solution can be verified using logarithmic space.

Question 10

Savitchs Theorem

Answer 10

shows that deterministic machines can simulate
nondeterministic machines by using a surprisingly
small amount of space

Question 11

PSPACE Complete

Answer 11

Language B is PSPACE COMPLETE if:
1. Is in PSPACE, and
2. Every A in PSPACE is polynomial-time reducible to B.