Why isn't P and P/poly trivially the same?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
Can one live in the U.S. and not use a credit card?
If nine coins are tossed, what is the probability that the number of heads is even?
Count each bit-position separately over many 64-bit bitmasks, with AVX but not AVX2
Called into a meeting and told we are being made redundant (laid off) and "not to share outside". Can I tell my partner?
What is Tony Stark injecting into himself in Iron Man 3?
Would those living in a "perfect society" not understand satire
Translation of 答えを知っている人はいませんでした
Short scifi story where reproductive organs are converted to produce "materials", pregnant protagonist is "found fit" to be a mother
How to copy the rest of lines of a file to another file
How do spaceships determine each other's mass in space?
What can I do if someone tampers with my SSH public key?
Can the Witch Sight warlock invocation see through the Mirror Image spell?
Does the US political system, in principle, allow for a no-party system?
What will happen if my luggage gets delayed?
"If + would" conditional in present perfect tense
Does an unused member variable take up memory?
Is divide-by-zero a security vulnerability?
One circle's diameter is different from others within a series of circles
Why is there an extra space when I type "ls" on the Desktop?
What is better: yes / no radio, or simple checkbox?
Cycles on the torus
How to write a chaotic neutral protagonist and prevent my readers from thinking they are evil?
Trocar background-image com delay via jQuery
Can't make sense of a paragraph from Lovecraft
Why isn't P and P/poly trivially the same?
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 yesterday
dcwdcw
513
New contributor
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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 yesterday
dcwdcw
513
New contributor
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
yesterday
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
yesterday
$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
yesterday
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
yesterday
|
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 yesterday
dcwdcw
513
New contributor
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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 yesterday
dcwdcw
513
New contributor
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
dcwdcw
513
New contributor
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
dcwdcw
513
New contributor
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
dcwdcw
513
asked yesterday
dcwdcw
513
513
New contributor
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
dcw is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
yesterday
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
yesterday
$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
yesterday
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
yesterday
|
show 1 more comment
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
yesterday
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
yesterday
$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
yesterday
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
yesterday
4
4
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
yesterday
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
yesterday
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
yesterday
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
yesterday
$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
yesterday
$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
yesterday
$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
yesterday
3
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
yesterday
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
yesterday
|
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 yesterday
David RicherbyDavid Richerby
68.1k15103194
$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
10 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
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
);
);
dcw is a new contributor. Be nice, and check out our Code of Conduct.
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 yesterday
David RicherbyDavid Richerby
68.1k15103194
$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
10 hours ago
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 yesterday
David RicherbyDavid Richerby
68.1k15103194
$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
10 hours ago
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 yesterday
David RicherbyDavid Richerby
68.1k15103194
$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 yesterday
David RicherbyDavid Richerby
68.1k15103194
answered yesterday
David RicherbyDavid Richerby
68.1k15103194
answered yesterday
David RicherbyDavid Richerby
68.1k15103194
answered yesterday
David RicherbyDavid Richerby
68.1k15103194
68.1k15103194
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
10 hours ago
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
10 hours ago
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
10 hours ago
$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
10 hours ago
add a comment |
dcw is a new contributor. Be nice, and check out our Code of Conduct.
dcw is a new contributor. Be nice, and check out our Code of Conduct.
dcw is a new contributor. Be nice, and check out our Code of Conduct.
dcw is a new contributor. Be nice, and check out our Code of Conduct.
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
yesterday
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
yesterday
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
yesterday
$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
yesterday
3
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
yesterday