HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

looking for a strongly NP Complete related problem

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemrelatedstronglylookingcompletefor

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#45227, answer score: 3

Revisions (0)

No revisions yet.