Tjyylli

Is divide-by-zero a security vulnerability?

How can I portion out frozen cookie dough?

How to make sure I'm assertive enough in contact with subordinates?

3.5% Interest Student Loan or use all of my savings on Tuition?

Was it really inappropriate to write a pull request for the company I interviewed with?

After Brexit, will the EU recognize British passports that are valid for more than ten years?

Exempt portion of equation line from aligning?

Short story about cities being connected by a conveyor belt

Should we avoid writing fiction about historical events without extensive research?

How to write a chaotic neutral protagonist and prevent my readers from thinking they are evil?

When Central Limit Theorem breaks down

I've given my players a lot of magic items. Is it reasonable for me to give them harder encounters?

How do you use environments that have the same name within a single latex document?

School performs periodic password audits. Is my password compromised?

Why isn't P and P/poly trivially the same?

How do you make a gun that shoots melee weapons and/or swords?

How to educate team mate to take screenshots for bugs with out unwanted stuff

Should I file my taxes? No income, unemployed, but paid 2k in student loan interest

Insult for someone who "doesn't know anything"

Professor forcing me to attend a conference, I can't afford even with 50% funding

Is "cogitate" used appropriately in "I cogitate that success relies on hard work"?

How spaceships determine each other's mass in space?

Precision notation for voltmeters

What does *dead* mean in *What do you mean, dead?*?

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 $mathsf{SIZE}(n^k)$ vs $mathsf{P/poly}$ and $mathsf{SIZE}(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

7

$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

share|cite|improve this question

asked 10 hours ago

dcwdcw

383

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
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
  $endgroup$
  – dcw
  10 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
  10 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
  10 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @dcw A language is in P if there is a Turing machine such that...
  $endgroup$
  – David Richerby
  10 hours ago
  

  
  
  
  

 | 
show 1 more comment

7

$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

share|cite|improve this question

asked 10 hours ago

dcwdcw

383

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
  10 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time?
  $endgroup$
  – dcw
  10 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
  10 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
  10 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @dcw A language is in P if there is a Turing machine such that...
  $endgroup$
  – David Richerby
  10 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

share|cite|improve this question

asked 10 hours ago

dcwdcw

383

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$

share|cite|improve this question

asked 10 hours ago

dcwdcw

383

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.

share|cite|improve this question

asked 10 hours ago

dcwdcw

383

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 10 hours ago

dcwdcw

383

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 10 hours ago

dcwdcw

383

1 Answer
1

active

oldest

votes

9

$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 $Ssubseteqmathbb{N}$, you could set declare $C_i=mathrm{true}$ if $iin S$ and $C_i=mathrm{false}$ for $inotin S$. Even if $S$ is undecidable!

In contrast, a language is in $mathrm{P}$ 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 $mathrm{P}$. But that's not necessarily enough to decide a language in $mathrm{P/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.

share|cite|improve this answer

answered 10 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.

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

9

$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 $Ssubseteqmathbb{N}$, you could set declare $C_i=mathrm{true}$ if $iin S$ and $C_i=mathrm{false}$ for $inotin S$. Even if $S$ is undecidable!

In contrast, a language is in $mathrm{P}$ 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 $mathrm{P}$. But that's not necessarily enough to decide a language in $mathrm{P/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.

share|cite|improve this answer

answered 10 hours ago

David RicherbyDavid Richerby

68k15102193

$endgroup$

add a comment | 

9

$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 $Ssubseteqmathbb{N}$, you could set declare $C_i=mathrm{true}$ if $iin S$ and $C_i=mathrm{false}$ for $inotin S$. Even if $S$ is undecidable!

In contrast, a language is in $mathrm{P}$ 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 $mathrm{P}$. But that's not necessarily enough to decide a language in $mathrm{P/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.

share|cite|improve this answer

answered 10 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 $Ssubseteqmathbb{N}$, you could set declare $C_i=mathrm{true}$ if $iin S$ and $C_i=mathrm{false}$ for $inotin S$. Even if $S$ is undecidable!

In contrast, a language is in $mathrm{P}$ 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 $mathrm{P}$. But that's not necessarily enough to decide a language in $mathrm{P/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.

share|cite|improve this answer

answered 10 hours ago

David RicherbyDavid Richerby

68k15102193

$endgroup$

share|cite|improve this answer

answered 10 hours ago

David RicherbyDavid Richerby

68k15102193

answered 10 hours ago

David RicherbyDavid Richerby

68k15102193

answered 10 hours ago

David RicherbyDavid Richerby

68k15102193