4
$\begingroup$

I'm looking for a problem that is NP-Complete (even) if the number of input values is at most a polylog of the input size. So some or each value in the input should be so large that the number of values is "negligable".

One way to do this is to say that there is only one input value that should be split and represents the input to another NPC problem. But I consider this a bypass and I'm looking for a more conventional problem.

According to Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded? and its answers, I cannot simply take a strongly NP-Complete problem and represent its input as unary.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ I don't understand what you are asking. What do you mean by "number of parameters is polylog of the input size"? The number of parameters is fixed (it is part of the problem specification). Let me try asking another way: what do you mean by a parameter? Do you have any example of a problem with a number of parameters of that sort, even if it isn't NP-complete? $\endgroup$
    – D.W. ♦
    Aug 13 '15 at 2:10
  • $\begingroup$ edited the question accordingly. I now name it input variable. For example, if I want to know if 3,4 and-or 5 can be added to 8, the input consists of those numbers and each of 3,4,5 and 8 is an input variable. I just mean one element from the input. $\endgroup$
    – Albert Hendriks
    Aug 13 '15 at 2:49
  • $\begingroup$ They also use the word "parameter" in the same way here. en.wikipedia.org/wiki/Strongly_NP-complete $\endgroup$
    – Albert Hendriks
    Aug 13 '15 at 2:55
  • $\begingroup$ Thanks for the edit. That helps. But now I have a new concern. It's easy to build a problem with this property by "padding": take any old NP-complete problem, and add some additional input variables that are ignored. Done. Looks like that meets all of the requirements explicitly stated in the question -- but I find it hard to believe that you're going to be happy with that answer. If this kind of answer is not useful to you, I think you're going to need to edit the question more to explain the motivation/context or explain what problem you're trying to solve or why you're asking. $\endgroup$
    – D.W. ♦
    Aug 13 '15 at 2:57
  • $\begingroup$ I edited to say "at most" a polylog. So by adding a lot of (small) input values, you'll get further away from that requirement. $\endgroup$
    – Albert Hendriks
    Aug 13 '15 at 3:11
3
$\begingroup$

Wikipedia's list of NP-complete problems lists the following problem:

Input: positive integers $A,B,C$
Question: do there exist positive integers $x,y$ such that $Ax^2+By-C=0$?

This is a NP-complete problem that has only 3 input values (which is certainly at most poly-log of the input size).

You can find another example of a NP-complete problem with only 3 input values at A Query regarding Quadratic Residuocity Problem.

Improve this answer
$\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.