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
If nine coins are tossed, what is the probability that the number of heads is even?
Why aren't there more Gauls like Obelix?
Why does a car's steering wheel get lighter with increasing speed
What does *dead* mean in *What do you mean, dead?*?
Should I file my taxes? No income, unemployed, but paid 2k in student loan interest
Use Mercury as quenching liquid for swords?
What is the orbit and expected lifetime of Crew Dragon trunk?
How do I get an FAA okay for a private runway?
After Brexit, will the EU recognize British passports that are valid for more than ten years?
Why restrict private health insurance?
Is "cogitate" used appropriately in "I cogitate that success relies on hard work"?
Is it a Cyclops number? "Nobody" knows!
Has a sovereign Communist government ever run, and conceded loss, on a fair election?
How spaceships determine each other's mass in space?
A running toilet that stops itself
Trigger on Custom Object Share
Generating a list with duplicate entries
Finding integer solution to a quadratic equation in two unknowns
EXM headers adding bounce@spe.sitecoremail.com as the sender
School performs periodic password audits. Is my password compromised?
Is this a crown race?
Why is my explanation wrong?
What is the best index strategy or query SELECT when performing a search/lookup BETWEEN IP address (IPv4 and IPv6) ranges?
Short story about cities being connected by a conveyor belt
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 3 hours ago
dcwdcw
233
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 3 hours ago
dcwdcw
233
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$
2
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
3 hours ago
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
3 hours ago
1
$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
3 hours ago
$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
3 hours ago
1
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
3 hours ago
|
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 3 hours ago
dcwdcw
233
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 3 hours ago
dcwdcw
233
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 3 hours ago
dcwdcw
233
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 3 hours ago
dcwdcw
233
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 3 hours ago
dcwdcw
233
asked 3 hours ago
dcwdcw
233
233
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.
2
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
3 hours ago
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
3 hours ago
1
$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
3 hours ago
$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
3 hours ago
1
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
3 hours ago
|
show 1 more comment
2
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
3 hours ago
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
3 hours ago
1
$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
3 hours ago
$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
3 hours ago
1
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
3 hours ago
2
2
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
3 hours ago
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
3 hours ago
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
3 hours ago
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
3 hours ago
1
1
$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
3 hours ago
$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
3 hours ago
$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
3 hours ago
$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
3 hours ago
1
1
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
3 hours ago
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
3 hours ago
|
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 3 hours ago
David RicherbyDavid Richerby
68k15102193
$endgroup$
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 3 hours ago
David RicherbyDavid Richerby
68k15102193
$endgroup$
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 3 hours ago
David RicherbyDavid Richerby
68k15102193
$endgroup$
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 3 hours ago
David RicherbyDavid Richerby
68k15102193
$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 3 hours ago
David RicherbyDavid Richerby
68k15102193
answered 3 hours ago
David RicherbyDavid Richerby
68k15102193
answered 3 hours ago
David RicherbyDavid Richerby
68k15102193
answered 3 hours ago
David RicherbyDavid Richerby
68k15102193
68k15102193
add a comment |
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
2
$begingroup$
P/poly can compute undecidable languages (exercise).
$endgroup$
– Yuval Filmus
3 hours ago
$begingroup$
Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
$endgroup$
– dcw
3 hours ago
1
$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
3 hours ago
$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
3 hours ago
1
$begingroup$
@dcw A language is in P if there is a Turing machine such that...
$endgroup$
– David Richerby
3 hours ago