3
$\begingroup$

Take this example mentioned here: NP-hard problems with very fast exponential-time algorithms

We can create such problem by padding assuming ETH‌. Take an NP-complete problem $L$ such that $L$ is decidable in time $O(2^n)$, by padding $L$ with some dummy 1's, create $L'=\{1^{n−(\log_21.01)n}x:|x|=(\log_21.01)n∧x∈L\}$. it is easy to prove that $L'$ is complete for NP and the running time of $L'$ is exactly $O(1.01^n)$.

Because I'm a newbie in mathematics and computer science, I don't quite understand this answer. Does it mean that padding an NP-problem that can be solved in $O(2^n)$ with a string of dummies 1, we can construct a new variant of the original problem that can be solved in fast exponential time $O(1.01^n)$?

As an additional question: can I apply this technique to Levin's universal search (http://www.scholarpedia.org/article/Universal_search)?

$\endgroup$
3
$\begingroup$

Here is a more extreme example: $$ \mathrm{SAT_{PAD}} = \{1^{2^n} 0 \phi : \text{$\phi$ is a satisfiable CNF on $n$ variables}\}. $$ This language is decidable in polynomial time.

What padding accomplishes is it constructs a language in a lower complexity class; it doesn't actually help you solve the original problem. All it does is artificially modify the parameter $n$.

Running an algorithm for $L$ on the language $L'$ results in a running time which is $O(1.01^n)$, where $n$ is the size of the padded instance; the running time is still $O(2^n)$ in terms of the size of the original instance.

I don't see any relevance to universal search. The main application of padding is to relate results about different complexity classes. For example, if P=NP then EXP=NEXP, since given any language in NEXP, you can pad it so that it is in NP, use the assumption to deduce that the padded language is in P, and then interpret the corresponding algorithm as proving that the original language is in EXP.

$\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.