Mixing
Help understanding this definition please? Probabilistically checkable proofs
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I'm having difficulty understanding the below.
Does this mean that the language L is an element of PCP which is made from two functions f(n) and g(n) which if there exists the polynomial time randomized oracle machine
- it takes input x and a random string r of big O of function f(n) where n is the size of the input
- theres a query set function Q (r,x) where r is the length, and x is the input, which produces several queries where the number of queries is the big O of the function g(n) - that is grows according to the growth size of g(n) depending on n
- where did y come from and what is it?
- makes a computation using the data and outputs My(r,x) which can either be 0 or 1.
is that correct?
what is y please?
and how is it used in the randomized oracle machine please
discrete-mathematics
asked Jul 18 at 16:31
Lilz
1163
add a comment |Â
up vote
2
down vote
favorite
I'm having difficulty understanding the below.
Does this mean that the language L is an element of PCP which is made from two functions f(n) and g(n) which if there exists the polynomial time randomized oracle machine
- it takes input x and a random string r of big O of function f(n) where n is the size of the input
- theres a query set function Q (r,x) where r is the length, and x is the input, which produces several queries where the number of queries is the big O of the function g(n) - that is grows according to the growth size of g(n) depending on n
- where did y come from and what is it?
- makes a computation using the data and outputs My(r,x) which can either be 0 or 1.
is that correct?
what is y please?
and how is it used in the randomized oracle machine please
discrete-mathematics
asked Jul 18 at 16:31
Lilz
1163
the $y$ are the oracle’s answers to the queries. It might help if you’re familiar with the oracle Turing machine definition of NP, which is a special case of this where the machine gets no random bits and a polynomial number of queries.
– spaceisdarkgreen
Jul 18 at 17:36
I should add that you have missed an important part about the randomness. If $xin L$ then there should be an oracle string (i.e. a proof) such that it accepts with at least a certain probability (usually one) and if $xnotin L$ then for any oracle string the machine should not accept with at least a certain probability (typically $1/2$)
– spaceisdarkgreen
Jul 18 at 22:06
soundness and completeness right?
– Lilz
Jul 18 at 22:53
also im not 100% clear on what exactly this LANGUAGE thing is... would it be all the code words generated or all the proofs ?
– Lilz
Jul 18 at 22:54
Yes, soundness/completeness. I will write an answer.
– spaceisdarkgreen
Jul 18 at 23:59
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm having difficulty understanding the below.
Does this mean that the language L is an element of PCP which is made from two functions f(n) and g(n) which if there exists the polynomial time randomized oracle machine
- it takes input x and a random string r of big O of function f(n) where n is the size of the input
- theres a query set function Q (r,x) where r is the length, and x is the input, which produces several queries where the number of queries is the big O of the function g(n) - that is grows according to the growth size of g(n) depending on n
- where did y come from and what is it?
- makes a computation using the data and outputs My(r,x) which can either be 0 or 1.
is that correct?
what is y please?
and how is it used in the randomized oracle machine please
discrete-mathematics
asked Jul 18 at 16:31
Lilz
1163
I'm having difficulty understanding the below.
Does this mean that the language L is an element of PCP which is made from two functions f(n) and g(n) which if there exists the polynomial time randomized oracle machine
- it takes input x and a random string r of big O of function f(n) where n is the size of the input
- theres a query set function Q (r,x) where r is the length, and x is the input, which produces several queries where the number of queries is the big O of the function g(n) - that is grows according to the growth size of g(n) depending on n
- where did y come from and what is it?
- makes a computation using the data and outputs My(r,x) which can either be 0 or 1.
is that correct?
what is y please?
and how is it used in the randomized oracle machine please
discrete-mathematics
asked Jul 18 at 16:31
Lilz
1163
asked Jul 18 at 16:31
Lilz
1163
asked Jul 18 at 16:31
Lilz
1163
asked Jul 18 at 16:31
Lilz
1163
1163
the $y$ are the oracle’s answers to the queries. It might help if you’re familiar with the oracle Turing machine definition of NP, which is a special case of this where the machine gets no random bits and a polynomial number of queries.
– spaceisdarkgreen
Jul 18 at 17:36
I should add that you have missed an important part about the randomness. If $xin L$ then there should be an oracle string (i.e. a proof) such that it accepts with at least a certain probability (usually one) and if $xnotin L$ then for any oracle string the machine should not accept with at least a certain probability (typically $1/2$)
– spaceisdarkgreen
Jul 18 at 22:06
soundness and completeness right?
– Lilz
Jul 18 at 22:53
also im not 100% clear on what exactly this LANGUAGE thing is... would it be all the code words generated or all the proofs ?
– Lilz
Jul 18 at 22:54
Yes, soundness/completeness. I will write an answer.
– spaceisdarkgreen
Jul 18 at 23:59
add a comment |Â
the $y$ are the oracle’s answers to the queries. It might help if you’re familiar with the oracle Turing machine definition of NP, which is a special case of this where the machine gets no random bits and a polynomial number of queries.
– spaceisdarkgreen
Jul 18 at 17:36
I should add that you have missed an important part about the randomness. If $xin L$ then there should be an oracle string (i.e. a proof) such that it accepts with at least a certain probability (usually one) and if $xnotin L$ then for any oracle string the machine should not accept with at least a certain probability (typically $1/2$)
– spaceisdarkgreen
Jul 18 at 22:06
soundness and completeness right?
– Lilz
Jul 18 at 22:53
also im not 100% clear on what exactly this LANGUAGE thing is... would it be all the code words generated or all the proofs ?
– Lilz
Jul 18 at 22:54
Yes, soundness/completeness. I will write an answer.
– spaceisdarkgreen
Jul 18 at 23:59
the $y$ are the oracle’s answers to the queries. It might help if you’re familiar with the oracle Turing machine definition of NP, which is a special case of this where the machine gets no random bits and a polynomial number of queries.
– spaceisdarkgreen
Jul 18 at 17:36
the $y$ are the oracle’s answers to the queries. It might help if you’re familiar with the oracle Turing machine definition of NP, which is a special case of this where the machine gets no random bits and a polynomial number of queries.
– spaceisdarkgreen
Jul 18 at 17:36
I should add that you have missed an important part about the randomness. If $xin L$ then there should be an oracle string (i.e. a proof) such that it accepts with at least a certain probability (usually one) and if $xnotin L$ then for any oracle string the machine should not accept with at least a certain probability (typically $1/2$)
– spaceisdarkgreen
Jul 18 at 22:06
I should add that you have missed an important part about the randomness. If $xin L$ then there should be an oracle string (i.e. a proof) such that it accepts with at least a certain probability (usually one) and if $xnotin L$ then for any oracle string the machine should not accept with at least a certain probability (typically $1/2$)
– spaceisdarkgreen
Jul 18 at 22:06
soundness and completeness right?
– Lilz
Jul 18 at 22:53
soundness and completeness right?
– Lilz
Jul 18 at 22:53
also im not 100% clear on what exactly this LANGUAGE thing is... would it be all the code words generated or all the proofs ?
– Lilz
Jul 18 at 22:54
also im not 100% clear on what exactly this LANGUAGE thing is... would it be all the code words generated or all the proofs ?
– Lilz
Jul 18 at 22:54
Yes, soundness/completeness. I will write an answer.
– spaceisdarkgreen
Jul 18 at 23:59
Yes, soundness/completeness. I will write an answer.
– spaceisdarkgreen
Jul 18 at 23:59
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
It's probably best to first understand NP in these terms, since most people have at least a decent intuition for what NP is. Informally, NP problems are ones whose solutions can be verified in polynomial time.
In this formalism, we say a language $L$ is in NP if there is a Turing machine such that for any string in $xin L$ there is an oracle string $y,$ whose size is polynomial in the size of $x$ such that the machine will accept on inputs $x$ and $y$ in polynomial time and if $xnotin L$ there is no oracle string $y$ such that the machine accepts on $x$ and $y$.
Here the input string $x$ is the 'problem' and the oracle string $y$ is the 'solution', and the Turing machine verifies that $y$ is a solution to $x$ (i.e. a proof that $xin L$) in polynomial time. To be more explicit the input strings under consideration could encode a weighted graph $G$ and a number $l$. The language $L$ could be the set of all strings that encode $(G,l)$ such that the graph $G$ has a Hamiltonian cycle of weight less than $l.$ So figuring out what strings are in $L$ is solving the traveling salesman problem. For any $(G,l)in L,$ there is a string $y$ (given to us by the oracle) that encodes a hamiltonian cycle on $G$ of weight less than $l$ and we can computationally verify in polynomial time that this is indeed the case. In other words, the traveling salesman problem is NP.
In PCP the situation is slightly different. Now, we are not necessarily presented with a full solution/proof but we only can ask the oracle a limited amount of information about it (before, we just demanded that the length of $y$ be polynomial in the length of $x$, which always allowed us to get the full solution, for instance the size of the description of a Hamiltonian cycle scales at most with the number of vertices). However, we are also allowed to use a randomized algorithm with some bounded amount of randomness, and we only demand probabilistic guarantees on whether we decide an input $x$ correctly or not. As I mentioned in the comments, we demand that we verify with absolute certainty when $xin L$ but we may have some false positives (up to $50%$ of the time) when $xnotin L.$ (Of course these numbers can be generalized.) So our randomized Turing machine asks its allotment of questions to the oracle about its purported solution, then in polynomial time decides if it's 'right as far as we can tell'. We demand that for $xin L$ there's always an oracle string that will convince our Turing machine, but when $xnotin L$ there may be oracle strings that fool our Turing machine into a false verification, but with low probability.
The most interesting case $PCP(log(n),1)$ has query size $g(n)=1,$ which means our algorithm can ask only a fixed number of questions about the solution, no matter how large the problem is, and it is allowed a logarithmic number of random bits. The PCP theorem says that $ PCP(log(n),1) = NP$. So for instance the traveling salesman problem is $PCP(log(n),1).$ Which means that there are some numbers $M$ and $C$ such that there is a randomized algorithm that takes an instance $(G,l)$ of the traveling salesman problem with size $n$ and uses $Clog(n)$ random bits. We have an oracle that has a purported proof there is a Hamiltonian cycle of weight less than $l$, but we don't know if it really is one or not. The random algorithm asks the oracle $M$ yes or no questions about its purported proof, and then, in polynomial time, decides whether it believes the oracle or not. The algorithm will always accept if the oracle really has a valid proof, and will not accept with >50% probability of the oracle does not.
Note that NP is a special case of $PCP(f(n),g(n)$, the theorem notwithstanding. We can express the definition of NP I gave in the second paragraph as $PCP(0,operatornamepoly(n)),$ in other words there is a deterministic polynomial time algorithm that will check the solution/proof (using a polynomial number of queries, though that's all you could use in a polynomial amount of time anyway.)
answered Jul 19 at 0:29
spaceisdarkgreen
27.5k21547
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
It's probably best to first understand NP in these terms, since most people have at least a decent intuition for what NP is. Informally, NP problems are ones whose solutions can be verified in polynomial time.
In this formalism, we say a language $L$ is in NP if there is a Turing machine such that for any string in $xin L$ there is an oracle string $y,$ whose size is polynomial in the size of $x$ such that the machine will accept on inputs $x$ and $y$ in polynomial time and if $xnotin L$ there is no oracle string $y$ such that the machine accepts on $x$ and $y$.
Here the input string $x$ is the 'problem' and the oracle string $y$ is the 'solution', and the Turing machine verifies that $y$ is a solution to $x$ (i.e. a proof that $xin L$) in polynomial time. To be more explicit the input strings under consideration could encode a weighted graph $G$ and a number $l$. The language $L$ could be the set of all strings that encode $(G,l)$ such that the graph $G$ has a Hamiltonian cycle of weight less than $l.$ So figuring out what strings are in $L$ is solving the traveling salesman problem. For any $(G,l)in L,$ there is a string $y$ (given to us by the oracle) that encodes a hamiltonian cycle on $G$ of weight less than $l$ and we can computationally verify in polynomial time that this is indeed the case. In other words, the traveling salesman problem is NP.
In PCP the situation is slightly different. Now, we are not necessarily presented with a full solution/proof but we only can ask the oracle a limited amount of information about it (before, we just demanded that the length of $y$ be polynomial in the length of $x$, which always allowed us to get the full solution, for instance the size of the description of a Hamiltonian cycle scales at most with the number of vertices). However, we are also allowed to use a randomized algorithm with some bounded amount of randomness, and we only demand probabilistic guarantees on whether we decide an input $x$ correctly or not. As I mentioned in the comments, we demand that we verify with absolute certainty when $xin L$ but we may have some false positives (up to $50%$ of the time) when $xnotin L.$ (Of course these numbers can be generalized.) So our randomized Turing machine asks its allotment of questions to the oracle about its purported solution, then in polynomial time decides if it's 'right as far as we can tell'. We demand that for $xin L$ there's always an oracle string that will convince our Turing machine, but when $xnotin L$ there may be oracle strings that fool our Turing machine into a false verification, but with low probability.
The most interesting case $PCP(log(n),1)$ has query size $g(n)=1,$ which means our algorithm can ask only a fixed number of questions about the solution, no matter how large the problem is, and it is allowed a logarithmic number of random bits. The PCP theorem says that $ PCP(log(n),1) = NP$. So for instance the traveling salesman problem is $PCP(log(n),1).$ Which means that there are some numbers $M$ and $C$ such that there is a randomized algorithm that takes an instance $(G,l)$ of the traveling salesman problem with size $n$ and uses $Clog(n)$ random bits. We have an oracle that has a purported proof there is a Hamiltonian cycle of weight less than $l$, but we don't know if it really is one or not. The random algorithm asks the oracle $M$ yes or no questions about its purported proof, and then, in polynomial time, decides whether it believes the oracle or not. The algorithm will always accept if the oracle really has a valid proof, and will not accept with >50% probability of the oracle does not.
Note that NP is a special case of $PCP(f(n),g(n)$, the theorem notwithstanding. We can express the definition of NP I gave in the second paragraph as $PCP(0,operatornamepoly(n)),$ in other words there is a deterministic polynomial time algorithm that will check the solution/proof (using a polynomial number of queries, though that's all you could use in a polynomial amount of time anyway.)
answered Jul 19 at 0:29
spaceisdarkgreen
27.5k21547
add a comment |Â
up vote
1
down vote
It's probably best to first understand NP in these terms, since most people have at least a decent intuition for what NP is. Informally, NP problems are ones whose solutions can be verified in polynomial time.
In this formalism, we say a language $L$ is in NP if there is a Turing machine such that for any string in $xin L$ there is an oracle string $y,$ whose size is polynomial in the size of $x$ such that the machine will accept on inputs $x$ and $y$ in polynomial time and if $xnotin L$ there is no oracle string $y$ such that the machine accepts on $x$ and $y$.
Here the input string $x$ is the 'problem' and the oracle string $y$ is the 'solution', and the Turing machine verifies that $y$ is a solution to $x$ (i.e. a proof that $xin L$) in polynomial time. To be more explicit the input strings under consideration could encode a weighted graph $G$ and a number $l$. The language $L$ could be the set of all strings that encode $(G,l)$ such that the graph $G$ has a Hamiltonian cycle of weight less than $l.$ So figuring out what strings are in $L$ is solving the traveling salesman problem. For any $(G,l)in L,$ there is a string $y$ (given to us by the oracle) that encodes a hamiltonian cycle on $G$ of weight less than $l$ and we can computationally verify in polynomial time that this is indeed the case. In other words, the traveling salesman problem is NP.
In PCP the situation is slightly different. Now, we are not necessarily presented with a full solution/proof but we only can ask the oracle a limited amount of information about it (before, we just demanded that the length of $y$ be polynomial in the length of $x$, which always allowed us to get the full solution, for instance the size of the description of a Hamiltonian cycle scales at most with the number of vertices). However, we are also allowed to use a randomized algorithm with some bounded amount of randomness, and we only demand probabilistic guarantees on whether we decide an input $x$ correctly or not. As I mentioned in the comments, we demand that we verify with absolute certainty when $xin L$ but we may have some false positives (up to $50%$ of the time) when $xnotin L.$ (Of course these numbers can be generalized.) So our randomized Turing machine asks its allotment of questions to the oracle about its purported solution, then in polynomial time decides if it's 'right as far as we can tell'. We demand that for $xin L$ there's always an oracle string that will convince our Turing machine, but when $xnotin L$ there may be oracle strings that fool our Turing machine into a false verification, but with low probability.
The most interesting case $PCP(log(n),1)$ has query size $g(n)=1,$ which means our algorithm can ask only a fixed number of questions about the solution, no matter how large the problem is, and it is allowed a logarithmic number of random bits. The PCP theorem says that $ PCP(log(n),1) = NP$. So for instance the traveling salesman problem is $PCP(log(n),1).$ Which means that there are some numbers $M$ and $C$ such that there is a randomized algorithm that takes an instance $(G,l)$ of the traveling salesman problem with size $n$ and uses $Clog(n)$ random bits. We have an oracle that has a purported proof there is a Hamiltonian cycle of weight less than $l$, but we don't know if it really is one or not. The random algorithm asks the oracle $M$ yes or no questions about its purported proof, and then, in polynomial time, decides whether it believes the oracle or not. The algorithm will always accept if the oracle really has a valid proof, and will not accept with >50% probability of the oracle does not.
Note that NP is a special case of $PCP(f(n),g(n)$, the theorem notwithstanding. We can express the definition of NP I gave in the second paragraph as $PCP(0,operatornamepoly(n)),$ in other words there is a deterministic polynomial time algorithm that will check the solution/proof (using a polynomial number of queries, though that's all you could use in a polynomial amount of time anyway.)
answered Jul 19 at 0:29
spaceisdarkgreen
27.5k21547
add a comment |Â
up vote
1
down vote
up vote
1
down vote
It's probably best to first understand NP in these terms, since most people have at least a decent intuition for what NP is. Informally, NP problems are ones whose solutions can be verified in polynomial time.
In this formalism, we say a language $L$ is in NP if there is a Turing machine such that for any string in $xin L$ there is an oracle string $y,$ whose size is polynomial in the size of $x$ such that the machine will accept on inputs $x$ and $y$ in polynomial time and if $xnotin L$ there is no oracle string $y$ such that the machine accepts on $x$ and $y$.
Here the input string $x$ is the 'problem' and the oracle string $y$ is the 'solution', and the Turing machine verifies that $y$ is a solution to $x$ (i.e. a proof that $xin L$) in polynomial time. To be more explicit the input strings under consideration could encode a weighted graph $G$ and a number $l$. The language $L$ could be the set of all strings that encode $(G,l)$ such that the graph $G$ has a Hamiltonian cycle of weight less than $l.$ So figuring out what strings are in $L$ is solving the traveling salesman problem. For any $(G,l)in L,$ there is a string $y$ (given to us by the oracle) that encodes a hamiltonian cycle on $G$ of weight less than $l$ and we can computationally verify in polynomial time that this is indeed the case. In other words, the traveling salesman problem is NP.
In PCP the situation is slightly different. Now, we are not necessarily presented with a full solution/proof but we only can ask the oracle a limited amount of information about it (before, we just demanded that the length of $y$ be polynomial in the length of $x$, which always allowed us to get the full solution, for instance the size of the description of a Hamiltonian cycle scales at most with the number of vertices). However, we are also allowed to use a randomized algorithm with some bounded amount of randomness, and we only demand probabilistic guarantees on whether we decide an input $x$ correctly or not. As I mentioned in the comments, we demand that we verify with absolute certainty when $xin L$ but we may have some false positives (up to $50%$ of the time) when $xnotin L.$ (Of course these numbers can be generalized.) So our randomized Turing machine asks its allotment of questions to the oracle about its purported solution, then in polynomial time decides if it's 'right as far as we can tell'. We demand that for $xin L$ there's always an oracle string that will convince our Turing machine, but when $xnotin L$ there may be oracle strings that fool our Turing machine into a false verification, but with low probability.
The most interesting case $PCP(log(n),1)$ has query size $g(n)=1,$ which means our algorithm can ask only a fixed number of questions about the solution, no matter how large the problem is, and it is allowed a logarithmic number of random bits. The PCP theorem says that $ PCP(log(n),1) = NP$. So for instance the traveling salesman problem is $PCP(log(n),1).$ Which means that there are some numbers $M$ and $C$ such that there is a randomized algorithm that takes an instance $(G,l)$ of the traveling salesman problem with size $n$ and uses $Clog(n)$ random bits. We have an oracle that has a purported proof there is a Hamiltonian cycle of weight less than $l$, but we don't know if it really is one or not. The random algorithm asks the oracle $M$ yes or no questions about its purported proof, and then, in polynomial time, decides whether it believes the oracle or not. The algorithm will always accept if the oracle really has a valid proof, and will not accept with >50% probability of the oracle does not.
Note that NP is a special case of $PCP(f(n),g(n)$, the theorem notwithstanding. We can express the definition of NP I gave in the second paragraph as $PCP(0,operatornamepoly(n)),$ in other words there is a deterministic polynomial time algorithm that will check the solution/proof (using a polynomial number of queries, though that's all you could use in a polynomial amount of time anyway.)
answered Jul 19 at 0:29
spaceisdarkgreen
27.5k21547
It's probably best to first understand NP in these terms, since most people have at least a decent intuition for what NP is. Informally, NP problems are ones whose solutions can be verified in polynomial time.
In this formalism, we say a language $L$ is in NP if there is a Turing machine such that for any string in $xin L$ there is an oracle string $y,$ whose size is polynomial in the size of $x$ such that the machine will accept on inputs $x$ and $y$ in polynomial time and if $xnotin L$ there is no oracle string $y$ such that the machine accepts on $x$ and $y$.
Here the input string $x$ is the 'problem' and the oracle string $y$ is the 'solution', and the Turing machine verifies that $y$ is a solution to $x$ (i.e. a proof that $xin L$) in polynomial time. To be more explicit the input strings under consideration could encode a weighted graph $G$ and a number $l$. The language $L$ could be the set of all strings that encode $(G,l)$ such that the graph $G$ has a Hamiltonian cycle of weight less than $l.$ So figuring out what strings are in $L$ is solving the traveling salesman problem. For any $(G,l)in L,$ there is a string $y$ (given to us by the oracle) that encodes a hamiltonian cycle on $G$ of weight less than $l$ and we can computationally verify in polynomial time that this is indeed the case. In other words, the traveling salesman problem is NP.
In PCP the situation is slightly different. Now, we are not necessarily presented with a full solution/proof but we only can ask the oracle a limited amount of information about it (before, we just demanded that the length of $y$ be polynomial in the length of $x$, which always allowed us to get the full solution, for instance the size of the description of a Hamiltonian cycle scales at most with the number of vertices). However, we are also allowed to use a randomized algorithm with some bounded amount of randomness, and we only demand probabilistic guarantees on whether we decide an input $x$ correctly or not. As I mentioned in the comments, we demand that we verify with absolute certainty when $xin L$ but we may have some false positives (up to $50%$ of the time) when $xnotin L.$ (Of course these numbers can be generalized.) So our randomized Turing machine asks its allotment of questions to the oracle about its purported solution, then in polynomial time decides if it's 'right as far as we can tell'. We demand that for $xin L$ there's always an oracle string that will convince our Turing machine, but when $xnotin L$ there may be oracle strings that fool our Turing machine into a false verification, but with low probability.
The most interesting case $PCP(log(n),1)$ has query size $g(n)=1,$ which means our algorithm can ask only a fixed number of questions about the solution, no matter how large the problem is, and it is allowed a logarithmic number of random bits. The PCP theorem says that $ PCP(log(n),1) = NP$. So for instance the traveling salesman problem is $PCP(log(n),1).$ Which means that there are some numbers $M$ and $C$ such that there is a randomized algorithm that takes an instance $(G,l)$ of the traveling salesman problem with size $n$ and uses $Clog(n)$ random bits. We have an oracle that has a purported proof there is a Hamiltonian cycle of weight less than $l$, but we don't know if it really is one or not. The random algorithm asks the oracle $M$ yes or no questions about its purported proof, and then, in polynomial time, decides whether it believes the oracle or not. The algorithm will always accept if the oracle really has a valid proof, and will not accept with >50% probability of the oracle does not.
Note that NP is a special case of $PCP(f(n),g(n)$, the theorem notwithstanding. We can express the definition of NP I gave in the second paragraph as $PCP(0,operatornamepoly(n)),$ in other words there is a deterministic polynomial time algorithm that will check the solution/proof (using a polynomial number of queries, though that's all you could use in a polynomial amount of time anyway.)
answered Jul 19 at 0:29
spaceisdarkgreen
27.5k21547
edited Jul 19 at 3:44
answered Jul 19 at 0:29
spaceisdarkgreen
27.5k21547
answered Jul 19 at 0:29
spaceisdarkgreen
27.5k21547
answered Jul 19 at 0:29
spaceisdarkgreen
27.5k21547
27.5k21547
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855746%2fhelp-understanding-this-definition-please-probabilistically-checkable-proofs%23new-answer', 'question_page');
);
Post as a guest
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
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
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
the $y$ are the oracle’s answers to the queries. It might help if you’re familiar with the oracle Turing machine definition of NP, which is a special case of this where the machine gets no random bits and a polynomial number of queries.
– spaceisdarkgreen
Jul 18 at 17:36
I should add that you have missed an important part about the randomness. If $xin L$ then there should be an oracle string (i.e. a proof) such that it accepts with at least a certain probability (usually one) and if $xnotin L$ then for any oracle string the machine should not accept with at least a certain probability (typically $1/2$)
– spaceisdarkgreen
Jul 18 at 22:06
soundness and completeness right?
– Lilz
Jul 18 at 22:53
also im not 100% clear on what exactly this LANGUAGE thing is... would it be all the code words generated or all the proofs ?
– Lilz
Jul 18 at 22:54
Yes, soundness/completeness. I will write an answer.
– spaceisdarkgreen
Jul 18 at 23:59