Question

Explain why the definition of PSPACE-complete problems uses polynomial-time reductibility rather than polynomial-space reducibility.

Thanks

Answer 1

• Solution :

  Non-deterministic Polynomial :

  Non-deterministic Polynomial (NP) is the set of decision problems solvable in the polynomial time by a non-deterministic machine.

  Non-deterministic Polynomial Completeness :

  If a known NP problem is solved using the given problem with modified input then the problem is NondeterministicPolynomial complete(NPC).

  The problems which are both in the NP and NP-hard are known as Nondeterministic Polynomial Complete problem.

  PSPACE-Complete :

  The problem is said to be PSPACE-complete if it is being solved using an amount of the memory that is polynomial in the input length.

  If the problem uses an amount of space polynomial in the size of its input, then it is called as  PSPACE-Complete.

  PROOF :

• 

so you see it takes poliunomial time to reduce the problem because elements of space can be resused by time just keeps on increasing