1
$\begingroup$

The first line of Sipser book for the Chapter- 'Time complexity', says that:

Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the solution requires an inordinate amount of time or memory.

My question is, yes we do have limited space and time, so the above statement makes the whole P and PSPACE concept as vague, right? If it so, what are these problems? Are such huge inputs acceptable in practice?

$\endgroup$
  • 2
    $\begingroup$ Cryptography is based on such problems. $\endgroup$ – Yuval Filmus Sep 13 at 6:20
  • $\begingroup$ Isn't cryptographic problem solution lies in undecidability currently? Please correct me if I am wrong. $\endgroup$ – Manika Sharma Sep 13 at 6:27
  • 1
    $\begingroup$ Cryptographic problems are trivially solvable in exponential time. $\endgroup$ – Yuval Filmus Sep 13 at 6:28
2
$\begingroup$

Given an integer k, are there integers (positive or negative) x, y, z with an absolute value ≤ $10^{1000}$ such that $x^3 + y^3 + z^3 = k$?

It is believed that without the limit on the absolute values the answer is "Yes" unless $k \equiv 4 \mod 9$ or $k \equiv 5 \mod 9$. On the other hand, solutions are so rare that most likely solutions for some values k cannot be found in the lifetime of the universe.

And both the inputs, and the space needed for a computation, are tiny. The limitation on the size of x, y, z makes it decidable.

$\endgroup$
1
$\begingroup$

If you consider space and time limitation, it'll be safe to assume that almost every Decidable problem (as per the exact definition) can have version that can be computationally not solvable.

That said, Turing machines are not a practical model for computing. Even in the theoretical computer science community, the more realistic RAM machines are used in the areas of algorithms and data structures. The concept of P - PSPACE are all dependent on Turing Machine, the method to classify a decidable/undecidable problem and hence must not be correlated with the practicality.

However, for sake of example:

  • Solving cryptographic problems can be considered as one of the example.

Relevant Stuff:

$\endgroup$

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.