2
$\begingroup$

I have a hypothetical question: suppose there exists an algorithm that solves an NP-Complete problem polynomial time, but requires the computation of values that grow exponentially big (or small).

For example, suppose POLY-3SAT solves 3-SAT in N^17, however to do so it must compute/evaluate the value of a number C whose value grows as N^1000 (or 1/N^1000).

What would this imply? Does computing/evaluating an exponentially large value automatically place the algorithm in EXP-SPACE (or some other complexity class)? It seems like this would be a different complexity class than just ordinary P.

Improve this question
$\endgroup$
3
  • $\begingroup$ @C Shreve "For example, suppose POLY-3SAT solves 3-SAT in N^17, ... " Do you know that $O(N^{17})$ is both impractical and infeasible for $N\ge10$, but in terms of computer science, the one who discovered this algorithm deserves a noble prize in computer science and 1,000,000$ for proving that P=NP. $\endgroup$
    – Farewell Stack Exchange
    Aug 16, 2017 at 16:08
  • 1
    $\begingroup$ @ErezZrihen The question says nothing about practical. I suspect the asker chose $n^{17}$ because it seems slightly easier to believe that there's an impractical, complicated polynomial-time algorithm for 3-SAT than that there's an $O(n^3)$ algorithm that nobody's noticed in all this time. $\endgroup$
    – David Richerby
    Aug 16, 2017 at 16:11
  • $\begingroup$ I also thought that it is possible to solve 3-SAT in $O(n^{24})$ time and someone commented me that algorithm with that complexity is practically unsolvable for $n \ge 10$, even though this comment didn't answer my question at all I still liked it, but you know it is just a comment not an answer. I just did as what he did in C Shreve's question. See this cs.stackexchange.com/questions/78015/…. This is gnasher729's first comment. $\endgroup$
    – Farewell Stack Exchange
    Aug 16, 2017 at 16:15

3 Answers 3

Reset to default
5
$\begingroup$

Complexity classes are classes of problems, not classes of algorithms. For example, the existence of Dijkstra's algorithm means that the problem of computing shortest paths in graphs is in P, but it doesn't make sense to say that "Dijkstra's algorithm is in P".

Exponentially large values can be stored in binary in a polynomial numebr of bits, and we can compute on such numbers using a polynomial number of operations. This notwithstanding, it seems that you're trying to get a polnomial-time algorithm that somehow dows exponentially much work, which is an oxymoron.

Improve this answer
$\endgroup$
3
$\begingroup$

It would imply that P = NP. The part about "values that grow exponentially big" is irrelevant; the same remark is true of any algorithm that solves a NP-complete problem in polynomial time.

A number whose value is as large as $N^{1000}$ is not a problem. It takes $1000 \lg N$ bits to represent such a number. You can add two such numbers in $O(\lg N)$ time, and multiply them in $O((\lg N)^2)$ time, which is polynomial in the input size.

Make sure you understand the difference between the size of the input and the input itself -- i.e., the difference between the value of a number and the number of bits needed to represent that number. I suggest you take a look at Relationship between an integer N and the number of bits n required to represent the integer, Complexity of multiplication, Time complexity of addition, Why addition algorithm is not pseudo- polynomial?, How can we assume that basic operations on numbers take constant time?.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This would still be the case if N was part of the exponential? For example C = $10^{N*1000}$? It just seems like P and P-With- Exponentially-Sized-Values should be different complexity classes. $\endgroup$
    – C Shreve
    Feb 23, 2017 at 0:08
  • 2
    $\begingroup$ @CShreve That still only takes $\Theta(N)$ bits to write down. $\endgroup$
    – David Richerby
    Feb 23, 2017 at 1:15
-2
$\begingroup$

If there exists an algorithm that solves NP-complete in P time and space then the values computed cannot grow exponentially. A problem in which the values computed grew exponentially would not be an NP-complete problem, as it could not be reduced to SAT by any P complexity algorithm.

The answers that the problem and not the algorithm are defining of complexity are incorrect. The problem has no inherent complexity. We say a problem is of X complexity based on the best known algorithm that can solve all possible instances of it. SAT defines the set of problems for which the best publicly known means to solve all possible instance was exponential in the number of variables (bits in the case of Boolean expressions).

However, given the time frame mentioned in arxiv.org/abs/cs/0205064 there existed a solution not publicly known to the specific problem before it the problem was publicly known and determined to not have a known P complexity solution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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