Why isn't P and P/poly trivially the same? Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Why does a polynomial-time language have a polynomial-sized circuit?Relation between logspace-uniform circuits and P-uniform circuitsPolynomial Identity Testing Evaluating a polynomial on a circuitHow to read $NC^1subset L subset NL subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?Difference between $mathsfSIZE(n^k)$ vs $mathsfP/poly$ and $mathsfSIZE(n)$ vs linear size circuit?*non-uniform* $ACC^0$ and above classesGiven snapshot and boolean circuit how to compute coNP formula?Boolean circuit with two inputs and advice input is hard-wired$Lin NC^1$ iff there exists a sequence of poly sized formulas that decides $L$Complexity class without fixed-poly size circuit
Tannaka duality for semisimple groups
What does this say in Elvish?
Project Euler #1 in C++
Maximum summed subsequences with non-adjacent items
Trademark violation for app?
Are sorcerers unable to use the Careful Spell metamagic option on themselves?
What would you call this weird metallic apparatus that allows you to lift people?
Lagrange four-squares theorem --- deterministic complexity
Why can't I install Tomboy in Ubuntu Mate 19.04?
Sum letters are not two different
What is the chair depicted in Cesare Maccari's 1889 painting "Cicerone denuncia Catilina"?
How can I prevent/balance waiting and turtling as a response to cooldown mechanics
What's the point of the test set?
If the probability of a dog barking one or more times in a given hour is 84%, then what is the probability of a dog barking in 30 minutes?
What is an "asse" in Elizabethan English?
Is there hard evidence that the grant peer review system performs significantly better than random?
The test team as an enemy of development? And how can this be avoided?
The Nth Gryphon Number
Crossing US/Canada Border for less than 24 hours
Google .dev domain strangely redirects to https
How to compare two different files line by line in unix?
If Windows 7 doesn't support WSL, then what is "Subsystem for UNIX-based Applications"?
Deconstruction is ambiguous
Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?
Why isn't P and P/poly trivially the same?
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Why does a polynomial-time language have a polynomial-sized circuit?Relation between logspace-uniform circuits and P-uniform circuitsPolynomial Identity Testing Evaluating a polynomial on a circuitHow to read $NC^1subset L subset NL subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?Difference between $mathsfSIZE(n^k)$ vs $mathsfP/poly$ and $mathsfSIZE(n)$ vs linear size circuit?*non-uniform* $ACC^0$ and above classesGiven snapshot and boolean circuit how to compute coNP formula?Boolean circuit with two inputs and advice input is hard-wired$Lin NC^1$ iff there exists a sequence of poly sized formulas that decides $L$Complexity class without fixed-poly size circuit
$begingroup$
The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can't a polynomial-sized circuit be simulated in polynomial time?
complexity-theory time-complexity circuits
asked Mar 8 at 20:07
dcwdcw
513
$endgroup$
|
show 1 more comment
$begingroup$
The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can't a polynomial-sized circuit be simulated in polynomial time?
complexity-theory time-complexity circuits
asked Mar 8 at 20:07
dcwdcw
513
$endgroup$
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
Mar 8 at 20:26
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
Mar 8 at 20:29
3
$begingroup$
It’s wrong. The polynomial size circuits for different input lengths could be radically different, and so cannot all be described by a single Turing machine.
$endgroup$
– Yuval Filmus
Mar 8 at 20:30
$begingroup$
Thanks, but where in the definition P does it say we're restricted to a single Turing machine? All the definitions I've seen are like in mathworld.wolfram.com/PolynomialTime.html
$endgroup$
– dcw
Mar 8 at 20:38
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
Mar 8 at 20:53
|
show 1 more comment
$begingroup$
The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can't a polynomial-sized circuit be simulated in polynomial time?
complexity-theory time-complexity circuits
asked Mar 8 at 20:07
dcwdcw
513
$endgroup$
The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can't a polynomial-sized circuit be simulated in polynomial time?
complexity-theory time-complexity circuits
complexity-theory time-complexity circuits
asked Mar 8 at 20:07
dcwdcw
513
asked Mar 8 at 20:07
dcwdcw
513
asked Mar 8 at 20:07
dcwdcw
513
asked Mar 8 at 20:07
dcwdcw
513
asked Mar 8 at 20:07
dcwdcw
513
513
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
Mar 8 at 20:26
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
Mar 8 at 20:29
3
$begingroup$
It’s wrong. The polynomial size circuits for different input lengths could be radically different, and so cannot all be described by a single Turing machine.
$endgroup$
– Yuval Filmus
Mar 8 at 20:30
$begingroup$
Thanks, but where in the definition P does it say we're restricted to a single Turing machine? All the definitions I've seen are like in mathworld.wolfram.com/PolynomialTime.html
$endgroup$
– dcw
Mar 8 at 20:38
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
Mar 8 at 20:53
|
show 1 more comment
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
Mar 8 at 20:26
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
Mar 8 at 20:29
3
$begingroup$
It’s wrong. The polynomial size circuits for different input lengths could be radically different, and so cannot all be described by a single Turing machine.
$endgroup$
– Yuval Filmus
Mar 8 at 20:30
$begingroup$
Thanks, but where in the definition P does it say we're restricted to a single Turing machine? All the definitions I've seen are like in mathworld.wolfram.com/PolynomialTime.html
$endgroup$
– dcw
Mar 8 at 20:38
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
Mar 8 at 20:53
4
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
Mar 8 at 20:26
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
Mar 8 at 20:26
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
Mar 8 at 20:29
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
Mar 8 at 20:29
3
3
$begingroup$
It’s wrong. The polynomial size circuits for different input lengths could be radically different, and so cannot all be described by a single Turing machine.
$endgroup$
– Yuval Filmus
Mar 8 at 20:30
$begingroup$
It’s wrong. The polynomial size circuits for different input lengths could be radically different, and so cannot all be described by a single Turing machine.
$endgroup$
– Yuval Filmus
Mar 8 at 20:30
$begingroup$
Thanks, but where in the definition P does it say we're restricted to a single Turing machine? All the definitions I've seen are like in mathworld.wolfram.com/PolynomialTime.html
$endgroup$
– dcw
Mar 8 at 20:38
$begingroup$
Thanks, but where in the definition P does it say we're restricted to a single Turing machine? All the definitions I've seen are like in mathworld.wolfram.com/PolynomialTime.html
$endgroup$
– dcw
Mar 8 at 20:38
3
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
Mar 8 at 20:53
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
Mar 8 at 20:53
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C_i$ and $C_i+1$: they could be completely different. In particular, for any set $SsubseteqmathbbN$, you could set declare $C_i=mathrmtrue$ if $iin S$ and $C_i=mathrmfalse$ for $inotin S$. Even if $S$ is undecidable!
In contrast, a language is in $mathrmP$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.
You're correct that we can evaluate any fixed circuit in $mathrmP$. But that's not necessarily enough to decide a language in $mathrmP/poly$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.
answered Mar 8 at 21:01
David RicherbyDavid Richerby
70.6k16107198
$endgroup$
1
$begingroup$
It's been years since I studied all this and I had (almost) forgotten the definition of $mathrmP/poly$, but reading this answer brought it all back: I remember having the same confusion when I first encountered the definition and arriving at the same resolution/understanding. :-)
$endgroup$
– ShreevatsaR
Mar 9 at 19:59
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: 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%2fcs.stackexchange.com%2fquestions%2f105350%2fwhy-isnt-p-and-p-poly-trivially-the-same%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$
The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C_i$ and $C_i+1$: they could be completely different. In particular, for any set $SsubseteqmathbbN$, you could set declare $C_i=mathrmtrue$ if $iin S$ and $C_i=mathrmfalse$ for $inotin S$. Even if $S$ is undecidable!
In contrast, a language is in $mathrmP$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.
You're correct that we can evaluate any fixed circuit in $mathrmP$. But that's not necessarily enough to decide a language in $mathrmP/poly$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.
answered Mar 8 at 21:01
David RicherbyDavid Richerby
70.6k16107198
$endgroup$
1
$begingroup$
It's been years since I studied all this and I had (almost) forgotten the definition of $mathrmP/poly$, but reading this answer brought it all back: I remember having the same confusion when I first encountered the definition and arriving at the same resolution/understanding. :-)
$endgroup$
– ShreevatsaR
Mar 9 at 19:59
add a comment |
$begingroup$
The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C_i$ and $C_i+1$: they could be completely different. In particular, for any set $SsubseteqmathbbN$, you could set declare $C_i=mathrmtrue$ if $iin S$ and $C_i=mathrmfalse$ for $inotin S$. Even if $S$ is undecidable!
In contrast, a language is in $mathrmP$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.
You're correct that we can evaluate any fixed circuit in $mathrmP$. But that's not necessarily enough to decide a language in $mathrmP/poly$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.
answered Mar 8 at 21:01
David RicherbyDavid Richerby
70.6k16107198
$endgroup$
1
$begingroup$
It's been years since I studied all this and I had (almost) forgotten the definition of $mathrmP/poly$, but reading this answer brought it all back: I remember having the same confusion when I first encountered the definition and arriving at the same resolution/understanding. :-)
$endgroup$
– ShreevatsaR
Mar 9 at 19:59
add a comment |
$begingroup$
The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C_i$ and $C_i+1$: they could be completely different. In particular, for any set $SsubseteqmathbbN$, you could set declare $C_i=mathrmtrue$ if $iin S$ and $C_i=mathrmfalse$ for $inotin S$. Even if $S$ is undecidable!
In contrast, a language is in $mathrmP$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.
You're correct that we can evaluate any fixed circuit in $mathrmP$. But that's not necessarily enough to decide a language in $mathrmP/poly$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.
answered Mar 8 at 21:01
David RicherbyDavid Richerby
70.6k16107198
$endgroup$
The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C_i$ and $C_i+1$: they could be completely different. In particular, for any set $SsubseteqmathbbN$, you could set declare $C_i=mathrmtrue$ if $iin S$ and $C_i=mathrmfalse$ for $inotin S$. Even if $S$ is undecidable!
In contrast, a language is in $mathrmP$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.
You're correct that we can evaluate any fixed circuit in $mathrmP$. But that's not necessarily enough to decide a language in $mathrmP/poly$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.
answered Mar 8 at 21:01
David RicherbyDavid Richerby
70.6k16107198
answered Mar 8 at 21:01
David RicherbyDavid Richerby
70.6k16107198
answered Mar 8 at 21:01
David RicherbyDavid Richerby
70.6k16107198
answered Mar 8 at 21:01
David RicherbyDavid Richerby
70.6k16107198
70.6k16107198
1
$begingroup$
It's been years since I studied all this and I had (almost) forgotten the definition of $mathrmP/poly$, but reading this answer brought it all back: I remember having the same confusion when I first encountered the definition and arriving at the same resolution/understanding. :-)
$endgroup$
– ShreevatsaR
Mar 9 at 19:59
add a comment |
1
$begingroup$
It's been years since I studied all this and I had (almost) forgotten the definition of $mathrmP/poly$, but reading this answer brought it all back: I remember having the same confusion when I first encountered the definition and arriving at the same resolution/understanding. :-)
$endgroup$
– ShreevatsaR
Mar 9 at 19:59
1
1
$begingroup$
It's been years since I studied all this and I had (almost) forgotten the definition of $mathrmP/poly$, but reading this answer brought it all back: I remember having the same confusion when I first encountered the definition and arriving at the same resolution/understanding. :-)
$endgroup$
– ShreevatsaR
Mar 9 at 19:59
$begingroup$
It's been years since I studied all this and I had (almost) forgotten the definition of $mathrmP/poly$, but reading this answer brought it all back: I remember having the same confusion when I first encountered the definition and arriving at the same resolution/understanding. :-)
$endgroup$
– ShreevatsaR
Mar 9 at 19:59
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- 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%2fcs.stackexchange.com%2fquestions%2f105350%2fwhy-isnt-p-and-p-poly-trivially-the-same%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
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
Mar 8 at 20:26
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
Mar 8 at 20:29
3
$begingroup$
It’s wrong. The polynomial size circuits for different input lengths could be radically different, and so cannot all be described by a single Turing machine.
$endgroup$
– Yuval Filmus
Mar 8 at 20:30
$begingroup$
Thanks, but where in the definition P does it say we're restricted to a single Turing machine? All the definitions I've seen are like in mathworld.wolfram.com/PolynomialTime.html
$endgroup$
– dcw
Mar 8 at 20:38
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
Mar 8 at 20:53