Naive question about polynomial time reducibilitySuper-linear time complexity lower bounds for any natural problem in NP?Solving NP problems in (usually) Polynomial time?Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?Proof that any NP problem can be reduced (in P time) to any problem in NPC?k-uniform k-partite hypergraph matching in polynomial timeWhat are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?Non-invertible Karp reduction
Naive question about polynomial time reducibility
Super-linear time complexity lower bounds for any natural problem in NP?Solving NP problems in (usually) Polynomial time?Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?Proof that any NP problem can be reduced (in P time) to any problem in NPC?k-uniform k-partite hypergraph matching in polynomial timeWhat are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?Non-invertible Karp reduction
$begingroup$
Question:
is it known, whether there is an upper bound on the exponent of the fastest polynomial-time reduction from $mathrm3SAT$ to $mathrmNP$-$mathrmhard$ problems or, can it be proved that for every problem requiring an $Theta(n^k)$ time reduction, there is a problem requiring an $Omega(n^k+1)$ reduction from $mathrm3SAT$?
Additional, secondary question:
Which $mathrmNP$-$mathrmhard$ problem requires the polynomial time reduction from $mathrm3SAT$ with the highest exponent?
computational-complexity
asked Sep 29 at 11:40
Manfred WeisManfred Weis
8,2582 gold badges16 silver badges48 bronze badges
$endgroup$
add a comment
|
$begingroup$
Question:
is it known, whether there is an upper bound on the exponent of the fastest polynomial-time reduction from $mathrm3SAT$ to $mathrmNP$-$mathrmhard$ problems or, can it be proved that for every problem requiring an $Theta(n^k)$ time reduction, there is a problem requiring an $Omega(n^k+1)$ reduction from $mathrm3SAT$?
Additional, secondary question:
Which $mathrmNP$-$mathrmhard$ problem requires the polynomial time reduction from $mathrm3SAT$ with the highest exponent?
computational-complexity
asked Sep 29 at 11:40
Manfred WeisManfred Weis
8,2582 gold badges16 silver badges48 bronze badges
$endgroup$
add a comment
|
$begingroup$
Question:
is it known, whether there is an upper bound on the exponent of the fastest polynomial-time reduction from $mathrm3SAT$ to $mathrmNP$-$mathrmhard$ problems or, can it be proved that for every problem requiring an $Theta(n^k)$ time reduction, there is a problem requiring an $Omega(n^k+1)$ reduction from $mathrm3SAT$?
Additional, secondary question:
Which $mathrmNP$-$mathrmhard$ problem requires the polynomial time reduction from $mathrm3SAT$ with the highest exponent?
computational-complexity
asked Sep 29 at 11:40
Manfred WeisManfred Weis
8,2582 gold badges16 silver badges48 bronze badges
$endgroup$
Question:
is it known, whether there is an upper bound on the exponent of the fastest polynomial-time reduction from $mathrm3SAT$ to $mathrmNP$-$mathrmhard$ problems or, can it be proved that for every problem requiring an $Theta(n^k)$ time reduction, there is a problem requiring an $Omega(n^k+1)$ reduction from $mathrm3SAT$?
Additional, secondary question:
Which $mathrmNP$-$mathrmhard$ problem requires the polynomial time reduction from $mathrm3SAT$ with the highest exponent?
computational-complexity
computational-complexity
asked Sep 29 at 11:40
Manfred WeisManfred Weis
8,2582 gold badges16 silver badges48 bronze badges
asked Sep 29 at 11:40
Manfred WeisManfred Weis
8,2582 gold badges16 silver badges48 bronze badges
asked Sep 29 at 11:40
Manfred WeisManfred Weis
8,2582 gold badges16 silver badges48 bronze badges
asked Sep 29 at 11:40
Manfred WeisManfred Weis
8,2582 gold badges16 silver badges48 bronze badges
asked Sep 29 at 11:40
Manfred WeisManfred Weis
8,2582 gold badges16 silver badges48 bronze badges
8,2582 gold badges16 silver badges48 bronze badges
add a comment
|
add a comment
|
1 Answer
1
active
oldest
votes
$begingroup$
It's unlikely there is any upper bound. To see the problem, consider the (artificial) problem
$text3SATpad = phi #^^100 : phi in text3SAT$,
where $#$ is some new symbol. $text3SATpad$ is in $mathsfNP$, and there is an obvious $O(n^100)$-time reduction from $text3SAT$ to $text3SATpad$. But it's doubtful there's even an $O(n^99)$-time reduction. Otherwise, one could solve $text3SAT$ in $2^O(n^.99)$ time (unlikely, as this violates the Exponential Time Hypothesis), as follows:
On input $phi$ of length $n$, run the reduction producing string $y$. The key point here is that $|y| leq O(n^99)$.
If $y$ is not of the form $psi #^^100$, reject.
Otherwise, since $|psi #^^100| leq O(n^99)$, it must be that $|psi| leq O(n^.99)$. Now decide if $psi in text3SAT$ in $2^O(n^.99)$ time, using a naive brute-force algorithm. This gives the correct answer about satisfiability of $phi$.
Perhaps one can even prove the impossibility conditioned only on $mathsfP neq mathsfNP$ (rather than on E.T.H.), by a Ladner's Theorem-type argument...
answered Sep 29 at 17:22
Ryan O'DonnellRyan O'Donnell
5,6891 gold badge22 silver badges42 bronze badges
$endgroup$
3
$begingroup$
Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem?
$endgroup$
– Emil Jeřábek supports Monica
Sep 29 at 17:44
$begingroup$
Seems possible, yes.
$endgroup$
– Ryan O'Donnell
Sep 29 at 17:50
1
$begingroup$
On second thoughts, it may not be so easy. The assumption that 3SAT reduces to any NP-complete language in $O(n^k)$ time implies (and is, in fact, equivalent to) that for every $LinmathrmNP$ and every constant $c$, $L$ can be decided by a deterministic polynomial-time computation (with exponent only depending on $L$) followed by an $O(n^1/c)$-time nondeterministic computation. However, I couldn’t get this to contradict the nondeterministic time hierarchy theorem.
$endgroup$
– Emil Jeřábek supports Monica
Sep 30 at 15:26
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "504"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f342720%2fnaive-question-about-polynomial-time-reducibility%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It's unlikely there is any upper bound. To see the problem, consider the (artificial) problem
$text3SATpad = phi #^^100 : phi in text3SAT$,
where $#$ is some new symbol. $text3SATpad$ is in $mathsfNP$, and there is an obvious $O(n^100)$-time reduction from $text3SAT$ to $text3SATpad$. But it's doubtful there's even an $O(n^99)$-time reduction. Otherwise, one could solve $text3SAT$ in $2^O(n^.99)$ time (unlikely, as this violates the Exponential Time Hypothesis), as follows:
On input $phi$ of length $n$, run the reduction producing string $y$. The key point here is that $|y| leq O(n^99)$.
If $y$ is not of the form $psi #^^100$, reject.
Otherwise, since $|psi #^^100| leq O(n^99)$, it must be that $|psi| leq O(n^.99)$. Now decide if $psi in text3SAT$ in $2^O(n^.99)$ time, using a naive brute-force algorithm. This gives the correct answer about satisfiability of $phi$.
Perhaps one can even prove the impossibility conditioned only on $mathsfP neq mathsfNP$ (rather than on E.T.H.), by a Ladner's Theorem-type argument...
answered Sep 29 at 17:22
Ryan O'DonnellRyan O'Donnell
5,6891 gold badge22 silver badges42 bronze badges
$endgroup$
3
$begingroup$
Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem?
$endgroup$
– Emil Jeřábek supports Monica
Sep 29 at 17:44
$begingroup$
Seems possible, yes.
$endgroup$
– Ryan O'Donnell
Sep 29 at 17:50
1
$begingroup$
On second thoughts, it may not be so easy. The assumption that 3SAT reduces to any NP-complete language in $O(n^k)$ time implies (and is, in fact, equivalent to) that for every $LinmathrmNP$ and every constant $c$, $L$ can be decided by a deterministic polynomial-time computation (with exponent only depending on $L$) followed by an $O(n^1/c)$-time nondeterministic computation. However, I couldn’t get this to contradict the nondeterministic time hierarchy theorem.
$endgroup$
– Emil Jeřábek supports Monica
Sep 30 at 15:26
add a comment
|
$begingroup$
It's unlikely there is any upper bound. To see the problem, consider the (artificial) problem
$text3SATpad = phi #^^100 : phi in text3SAT$,
where $#$ is some new symbol. $text3SATpad$ is in $mathsfNP$, and there is an obvious $O(n^100)$-time reduction from $text3SAT$ to $text3SATpad$. But it's doubtful there's even an $O(n^99)$-time reduction. Otherwise, one could solve $text3SAT$ in $2^O(n^.99)$ time (unlikely, as this violates the Exponential Time Hypothesis), as follows:
On input $phi$ of length $n$, run the reduction producing string $y$. The key point here is that $|y| leq O(n^99)$.
If $y$ is not of the form $psi #^^100$, reject.
Otherwise, since $|psi #^^100| leq O(n^99)$, it must be that $|psi| leq O(n^.99)$. Now decide if $psi in text3SAT$ in $2^O(n^.99)$ time, using a naive brute-force algorithm. This gives the correct answer about satisfiability of $phi$.
Perhaps one can even prove the impossibility conditioned only on $mathsfP neq mathsfNP$ (rather than on E.T.H.), by a Ladner's Theorem-type argument...
answered Sep 29 at 17:22
Ryan O'DonnellRyan O'Donnell
5,6891 gold badge22 silver badges42 bronze badges
$endgroup$
3
$begingroup$
Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem?
$endgroup$
– Emil Jeřábek supports Monica
Sep 29 at 17:44
$begingroup$
Seems possible, yes.
$endgroup$
– Ryan O'Donnell
Sep 29 at 17:50
1
$begingroup$
On second thoughts, it may not be so easy. The assumption that 3SAT reduces to any NP-complete language in $O(n^k)$ time implies (and is, in fact, equivalent to) that for every $LinmathrmNP$ and every constant $c$, $L$ can be decided by a deterministic polynomial-time computation (with exponent only depending on $L$) followed by an $O(n^1/c)$-time nondeterministic computation. However, I couldn’t get this to contradict the nondeterministic time hierarchy theorem.
$endgroup$
– Emil Jeřábek supports Monica
Sep 30 at 15:26
add a comment
|
$begingroup$
It's unlikely there is any upper bound. To see the problem, consider the (artificial) problem
$text3SATpad = phi #^^100 : phi in text3SAT$,
where $#$ is some new symbol. $text3SATpad$ is in $mathsfNP$, and there is an obvious $O(n^100)$-time reduction from $text3SAT$ to $text3SATpad$. But it's doubtful there's even an $O(n^99)$-time reduction. Otherwise, one could solve $text3SAT$ in $2^O(n^.99)$ time (unlikely, as this violates the Exponential Time Hypothesis), as follows:
On input $phi$ of length $n$, run the reduction producing string $y$. The key point here is that $|y| leq O(n^99)$.
If $y$ is not of the form $psi #^^100$, reject.
Otherwise, since $|psi #^^100| leq O(n^99)$, it must be that $|psi| leq O(n^.99)$. Now decide if $psi in text3SAT$ in $2^O(n^.99)$ time, using a naive brute-force algorithm. This gives the correct answer about satisfiability of $phi$.
Perhaps one can even prove the impossibility conditioned only on $mathsfP neq mathsfNP$ (rather than on E.T.H.), by a Ladner's Theorem-type argument...
answered Sep 29 at 17:22
Ryan O'DonnellRyan O'Donnell
5,6891 gold badge22 silver badges42 bronze badges
$endgroup$
It's unlikely there is any upper bound. To see the problem, consider the (artificial) problem
$text3SATpad = phi #^^100 : phi in text3SAT$,
where $#$ is some new symbol. $text3SATpad$ is in $mathsfNP$, and there is an obvious $O(n^100)$-time reduction from $text3SAT$ to $text3SATpad$. But it's doubtful there's even an $O(n^99)$-time reduction. Otherwise, one could solve $text3SAT$ in $2^O(n^.99)$ time (unlikely, as this violates the Exponential Time Hypothesis), as follows:
On input $phi$ of length $n$, run the reduction producing string $y$. The key point here is that $|y| leq O(n^99)$.
If $y$ is not of the form $psi #^^100$, reject.
Otherwise, since $|psi #^^100| leq O(n^99)$, it must be that $|psi| leq O(n^.99)$. Now decide if $psi in text3SAT$ in $2^O(n^.99)$ time, using a naive brute-force algorithm. This gives the correct answer about satisfiability of $phi$.
Perhaps one can even prove the impossibility conditioned only on $mathsfP neq mathsfNP$ (rather than on E.T.H.), by a Ladner's Theorem-type argument...
answered Sep 29 at 17:22
Ryan O'DonnellRyan O'Donnell
5,6891 gold badge22 silver badges42 bronze badges
answered Sep 29 at 17:22
Ryan O'DonnellRyan O'Donnell
5,6891 gold badge22 silver badges42 bronze badges
answered Sep 29 at 17:22
Ryan O'DonnellRyan O'Donnell
5,6891 gold badge22 silver badges42 bronze badges
answered Sep 29 at 17:22
Ryan O'DonnellRyan O'Donnell
5,6891 gold badge22 silver badges42 bronze badges
5,6891 gold badge22 silver badges42 bronze badges
3
$begingroup$
Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem?
$endgroup$
– Emil Jeřábek supports Monica
Sep 29 at 17:44
$begingroup$
Seems possible, yes.
$endgroup$
– Ryan O'Donnell
Sep 29 at 17:50
1
$begingroup$
On second thoughts, it may not be so easy. The assumption that 3SAT reduces to any NP-complete language in $O(n^k)$ time implies (and is, in fact, equivalent to) that for every $LinmathrmNP$ and every constant $c$, $L$ can be decided by a deterministic polynomial-time computation (with exponent only depending on $L$) followed by an $O(n^1/c)$-time nondeterministic computation. However, I couldn’t get this to contradict the nondeterministic time hierarchy theorem.
$endgroup$
– Emil Jeřábek supports Monica
Sep 30 at 15:26
add a comment
|
3
$begingroup$
Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem?
$endgroup$
– Emil Jeřábek supports Monica
Sep 29 at 17:44
$begingroup$
Seems possible, yes.
$endgroup$
– Ryan O'Donnell
Sep 29 at 17:50
1
$begingroup$
On second thoughts, it may not be so easy. The assumption that 3SAT reduces to any NP-complete language in $O(n^k)$ time implies (and is, in fact, equivalent to) that for every $LinmathrmNP$ and every constant $c$, $L$ can be decided by a deterministic polynomial-time computation (with exponent only depending on $L$) followed by an $O(n^1/c)$-time nondeterministic computation. However, I couldn’t get this to contradict the nondeterministic time hierarchy theorem.
$endgroup$
– Emil Jeřábek supports Monica
Sep 30 at 15:26
3
3
$begingroup$
Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem?
$endgroup$
– Emil Jeřábek supports Monica
Sep 29 at 17:44
$begingroup$
Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem?
$endgroup$
– Emil Jeřábek supports Monica
Sep 29 at 17:44
$begingroup$
Seems possible, yes.
$endgroup$
– Ryan O'Donnell
Sep 29 at 17:50
$begingroup$
Seems possible, yes.
$endgroup$
– Ryan O'Donnell
Sep 29 at 17:50
1
1
$begingroup$
On second thoughts, it may not be so easy. The assumption that 3SAT reduces to any NP-complete language in $O(n^k)$ time implies (and is, in fact, equivalent to) that for every $LinmathrmNP$ and every constant $c$, $L$ can be decided by a deterministic polynomial-time computation (with exponent only depending on $L$) followed by an $O(n^1/c)$-time nondeterministic computation. However, I couldn’t get this to contradict the nondeterministic time hierarchy theorem.
$endgroup$
– Emil Jeřábek supports Monica
Sep 30 at 15:26
$begingroup$
On second thoughts, it may not be so easy. The assumption that 3SAT reduces to any NP-complete language in $O(n^k)$ time implies (and is, in fact, equivalent to) that for every $LinmathrmNP$ and every constant $c$, $L$ can be decided by a deterministic polynomial-time computation (with exponent only depending on $L$) followed by an $O(n^1/c)$-time nondeterministic computation. However, I couldn’t get this to contradict the nondeterministic time hierarchy theorem.
$endgroup$
– Emil Jeřábek supports Monica
Sep 30 at 15:26
add a comment
|
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f342720%2fnaive-question-about-polynomial-time-reducibility%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
