Mixing
![Topology of $(-2,-1) cup D[0,1] cup 1,2$](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
What does this proof mean?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I'm having difficulty reading these proofs,
Definition 1 $V$ is an NP-verifier for $L$ if $V$ is polynomial-time in the length of the first input and that the following two properties hold:
- (completeness) If $x in L$, $exists pi: V(x,pi) = 1$.
- (soundness) If $x notin L$, $forall pi : V(x,pi) = 0$.
(Original image)
so the completeness one would be, if $x$ is an element of $L$ (part of the set $L$), there exists a $pi$ that is ????
and the soundness one is if $x$ is not an element of $L$ (not part of the set $L$), every $pi$ is not ????
Can anyone help me fill in the missing pieces?
Thank you
computer-science computational-complexity proof-theory
edited Jul 15 at 15:20
Jendrik Stelzner
7,55211037
asked Jul 15 at 14:55
Lilz
1163
add a comment |Â
up vote
0
down vote
favorite
I'm having difficulty reading these proofs,
Definition 1 $V$ is an NP-verifier for $L$ if $V$ is polynomial-time in the length of the first input and that the following two properties hold:
- (completeness) If $x in L$, $exists pi: V(x,pi) = 1$.
- (soundness) If $x notin L$, $forall pi : V(x,pi) = 0$.
(Original image)
so the completeness one would be, if $x$ is an element of $L$ (part of the set $L$), there exists a $pi$ that is ????
and the soundness one is if $x$ is not an element of $L$ (not part of the set $L$), every $pi$ is not ????
Can anyone help me fill in the missing pieces?
Thank you
computer-science computational-complexity proof-theory
edited Jul 15 at 15:20
Jendrik Stelzner
7,55211037
asked Jul 15 at 14:55
Lilz
1163
Reading the Wikipedia entry on a NP verify should help. Digits $1$ and $0$ may stand for $yes$ or $true $ and $no $ respectively.en.m.wikipedia.org/wiki/NP_(complexity)
– AnyAD
Jul 15 at 15:04
okay so am I correct in saying the completeness one would be, if x is an element of L, there exists a pi where function V(x, pi) = false ?
– Lilz
Jul 15 at 15:17
6
That's not a proof at all. It's a definition.
– Henning Makholm
Jul 15 at 15:27
sorry you're right. would the definition be correct: if x is an element of L, there exists a pi where function V(x, pi) = false
– Lilz
Jul 15 at 16:22
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I'm having difficulty reading these proofs,
Definition 1 $V$ is an NP-verifier for $L$ if $V$ is polynomial-time in the length of the first input and that the following two properties hold:
- (completeness) If $x in L$, $exists pi: V(x,pi) = 1$.
- (soundness) If $x notin L$, $forall pi : V(x,pi) = 0$.
(Original image)
so the completeness one would be, if $x$ is an element of $L$ (part of the set $L$), there exists a $pi$ that is ????
and the soundness one is if $x$ is not an element of $L$ (not part of the set $L$), every $pi$ is not ????
Can anyone help me fill in the missing pieces?
Thank you
computer-science computational-complexity proof-theory
edited Jul 15 at 15:20
Jendrik Stelzner
7,55211037
asked Jul 15 at 14:55
Lilz
1163
I'm having difficulty reading these proofs,
Definition 1 $V$ is an NP-verifier for $L$ if $V$ is polynomial-time in the length of the first input and that the following two properties hold:
- (completeness) If $x in L$, $exists pi: V(x,pi) = 1$.
- (soundness) If $x notin L$, $forall pi : V(x,pi) = 0$.
(Original image)
so the completeness one would be, if $x$ is an element of $L$ (part of the set $L$), there exists a $pi$ that is ????
and the soundness one is if $x$ is not an element of $L$ (not part of the set $L$), every $pi$ is not ????
Can anyone help me fill in the missing pieces?
Thank you
computer-science computational-complexity proof-theory
edited Jul 15 at 15:20
Jendrik Stelzner
7,55211037
asked Jul 15 at 14:55
Lilz
1163
edited Jul 15 at 15:20
Jendrik Stelzner
7,55211037
edited Jul 15 at 15:20
Jendrik Stelzner
7,55211037
edited Jul 15 at 15:20
Jendrik Stelzner
7,55211037
7,55211037
asked Jul 15 at 14:55
Lilz
1163
asked Jul 15 at 14:55
Lilz
1163
asked Jul 15 at 14:55
Lilz
1163
1163
Reading the Wikipedia entry on a NP verify should help. Digits $1$ and $0$ may stand for $yes$ or $true $ and $no $ respectively.en.m.wikipedia.org/wiki/NP_(complexity)
– AnyAD
Jul 15 at 15:04
okay so am I correct in saying the completeness one would be, if x is an element of L, there exists a pi where function V(x, pi) = false ?
– Lilz
Jul 15 at 15:17
6
That's not a proof at all. It's a definition.
– Henning Makholm
Jul 15 at 15:27
sorry you're right. would the definition be correct: if x is an element of L, there exists a pi where function V(x, pi) = false
– Lilz
Jul 15 at 16:22
add a comment |Â
Reading the Wikipedia entry on a NP verify should help. Digits $1$ and $0$ may stand for $yes$ or $true $ and $no $ respectively.en.m.wikipedia.org/wiki/NP_(complexity)
– AnyAD
Jul 15 at 15:04
okay so am I correct in saying the completeness one would be, if x is an element of L, there exists a pi where function V(x, pi) = false ?
– Lilz
Jul 15 at 15:17
6
That's not a proof at all. It's a definition.
– Henning Makholm
Jul 15 at 15:27
sorry you're right. would the definition be correct: if x is an element of L, there exists a pi where function V(x, pi) = false
– Lilz
Jul 15 at 16:22
Reading the Wikipedia entry on a NP verify should help. Digits $1$ and $0$ may stand for $yes$ or $true $ and $no $ respectively.en.m.wikipedia.org/wiki/NP_(complexity)
– AnyAD
Jul 15 at 15:04
Reading the Wikipedia entry on a NP verify should help. Digits $1$ and $0$ may stand for $yes$ or $true $ and $no $ respectively.en.m.wikipedia.org/wiki/NP_(complexity)
– AnyAD
Jul 15 at 15:04
okay so am I correct in saying the completeness one would be, if x is an element of L, there exists a pi where function V(x, pi) = false ?
– Lilz
Jul 15 at 15:17
okay so am I correct in saying the completeness one would be, if x is an element of L, there exists a pi where function V(x, pi) = false ?
– Lilz
Jul 15 at 15:17
6
6
That's not a proof at all. It's a definition.
– Henning Makholm
Jul 15 at 15:27
That's not a proof at all. It's a definition.
– Henning Makholm
Jul 15 at 15:27
sorry you're right. would the definition be correct: if x is an element of L, there exists a pi where function V(x, pi) = false
– Lilz
Jul 15 at 16:22
sorry you're right. would the definition be correct: if x is an element of L, there exists a pi where function V(x, pi) = false
– Lilz
Jul 15 at 16:22
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
Intuitively, you should think of $V$ as an algorithm that, given $x$ and an alleged reason $pi$ for believing that $xin L$, either says "Yes, I'm convinced that $xin L$" (coded as output $1$) or says "I'm not convinced; $x$ might be in $L$, but this $pi$ doesn't convince me" (coded as output $0$). Completeness says that, if $xin L$, then there is some way to convince $V$ to believe it, i.e., some $pi$ that will make $V$ produce the output $1$ (meaning "I'm convinced"). Soundness says that, if $xnotin L$, then nothing can fool $V$ into thinking that $xin L$, i.e., no matter what alleged reason $pi$ we provide, $V$ will give output $0$ (meaning "I'm not convinced").
answered Jul 15 at 18:27
Andreas Blass
47.6k348104
thank you that was very clear. so in that case, À is a variable representing a reason?
– Lilz
Jul 15 at 19:34
1
$pi$ is certainly a variable here. Notice that it is quantified in both Completeness and Soundness; only variables can be quantified. As for "representing a reason", that's how I think of it. Other people say "witness" rather than "reason"; their intuitive picture is that $pi$ testifies to the claim that $xin L$.
– Andreas Blass
Jul 15 at 20:03
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Intuitively, you should think of $V$ as an algorithm that, given $x$ and an alleged reason $pi$ for believing that $xin L$, either says "Yes, I'm convinced that $xin L$" (coded as output $1$) or says "I'm not convinced; $x$ might be in $L$, but this $pi$ doesn't convince me" (coded as output $0$). Completeness says that, if $xin L$, then there is some way to convince $V$ to believe it, i.e., some $pi$ that will make $V$ produce the output $1$ (meaning "I'm convinced"). Soundness says that, if $xnotin L$, then nothing can fool $V$ into thinking that $xin L$, i.e., no matter what alleged reason $pi$ we provide, $V$ will give output $0$ (meaning "I'm not convinced").
answered Jul 15 at 18:27
Andreas Blass
47.6k348104
thank you that was very clear. so in that case, À is a variable representing a reason?
– Lilz
Jul 15 at 19:34
1
$pi$ is certainly a variable here. Notice that it is quantified in both Completeness and Soundness; only variables can be quantified. As for "representing a reason", that's how I think of it. Other people say "witness" rather than "reason"; their intuitive picture is that $pi$ testifies to the claim that $xin L$.
– Andreas Blass
Jul 15 at 20:03
add a comment |Â
up vote
3
down vote
Intuitively, you should think of $V$ as an algorithm that, given $x$ and an alleged reason $pi$ for believing that $xin L$, either says "Yes, I'm convinced that $xin L$" (coded as output $1$) or says "I'm not convinced; $x$ might be in $L$, but this $pi$ doesn't convince me" (coded as output $0$). Completeness says that, if $xin L$, then there is some way to convince $V$ to believe it, i.e., some $pi$ that will make $V$ produce the output $1$ (meaning "I'm convinced"). Soundness says that, if $xnotin L$, then nothing can fool $V$ into thinking that $xin L$, i.e., no matter what alleged reason $pi$ we provide, $V$ will give output $0$ (meaning "I'm not convinced").
answered Jul 15 at 18:27
Andreas Blass
47.6k348104
thank you that was very clear. so in that case, À is a variable representing a reason?
– Lilz
Jul 15 at 19:34
1
$pi$ is certainly a variable here. Notice that it is quantified in both Completeness and Soundness; only variables can be quantified. As for "representing a reason", that's how I think of it. Other people say "witness" rather than "reason"; their intuitive picture is that $pi$ testifies to the claim that $xin L$.
– Andreas Blass
Jul 15 at 20:03
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Intuitively, you should think of $V$ as an algorithm that, given $x$ and an alleged reason $pi$ for believing that $xin L$, either says "Yes, I'm convinced that $xin L$" (coded as output $1$) or says "I'm not convinced; $x$ might be in $L$, but this $pi$ doesn't convince me" (coded as output $0$). Completeness says that, if $xin L$, then there is some way to convince $V$ to believe it, i.e., some $pi$ that will make $V$ produce the output $1$ (meaning "I'm convinced"). Soundness says that, if $xnotin L$, then nothing can fool $V$ into thinking that $xin L$, i.e., no matter what alleged reason $pi$ we provide, $V$ will give output $0$ (meaning "I'm not convinced").
answered Jul 15 at 18:27
Andreas Blass
47.6k348104
Intuitively, you should think of $V$ as an algorithm that, given $x$ and an alleged reason $pi$ for believing that $xin L$, either says "Yes, I'm convinced that $xin L$" (coded as output $1$) or says "I'm not convinced; $x$ might be in $L$, but this $pi$ doesn't convince me" (coded as output $0$). Completeness says that, if $xin L$, then there is some way to convince $V$ to believe it, i.e., some $pi$ that will make $V$ produce the output $1$ (meaning "I'm convinced"). Soundness says that, if $xnotin L$, then nothing can fool $V$ into thinking that $xin L$, i.e., no matter what alleged reason $pi$ we provide, $V$ will give output $0$ (meaning "I'm not convinced").
answered Jul 15 at 18:27
Andreas Blass
47.6k348104
answered Jul 15 at 18:27
Andreas Blass
47.6k348104
answered Jul 15 at 18:27
Andreas Blass
47.6k348104
answered Jul 15 at 18:27
Andreas Blass
47.6k348104
47.6k348104
thank you that was very clear. so in that case, À is a variable representing a reason?
– Lilz
Jul 15 at 19:34
1
$pi$ is certainly a variable here. Notice that it is quantified in both Completeness and Soundness; only variables can be quantified. As for "representing a reason", that's how I think of it. Other people say "witness" rather than "reason"; their intuitive picture is that $pi$ testifies to the claim that $xin L$.
– Andreas Blass
Jul 15 at 20:03
add a comment |Â
thank you that was very clear. so in that case, À is a variable representing a reason?
– Lilz
Jul 15 at 19:34
1
$pi$ is certainly a variable here. Notice that it is quantified in both Completeness and Soundness; only variables can be quantified. As for "representing a reason", that's how I think of it. Other people say "witness" rather than "reason"; their intuitive picture is that $pi$ testifies to the claim that $xin L$.
– Andreas Blass
Jul 15 at 20:03
thank you that was very clear. so in that case, À is a variable representing a reason?
– Lilz
Jul 15 at 19:34
thank you that was very clear. so in that case, À is a variable representing a reason?
– Lilz
Jul 15 at 19:34
1
1
$pi$ is certainly a variable here. Notice that it is quantified in both Completeness and Soundness; only variables can be quantified. As for "representing a reason", that's how I think of it. Other people say "witness" rather than "reason"; their intuitive picture is that $pi$ testifies to the claim that $xin L$.
– Andreas Blass
Jul 15 at 20:03
$pi$ is certainly a variable here. Notice that it is quantified in both Completeness and Soundness; only variables can be quantified. As for "representing a reason", that's how I think of it. Other people say "witness" rather than "reason"; their intuitive picture is that $pi$ testifies to the claim that $xin L$.
– Andreas Blass
Jul 15 at 20:03
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%2f2852598%2fwhat-does-this-proof-mean%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
Reading the Wikipedia entry on a NP verify should help. Digits $1$ and $0$ may stand for $yes$ or $true $ and $no $ respectively.en.m.wikipedia.org/wiki/NP_(complexity)
– AnyAD
Jul 15 at 15:04
okay so am I correct in saying the completeness one would be, if x is an element of L, there exists a pi where function V(x, pi) = false ?
– Lilz
Jul 15 at 15:17
6
That's not a proof at all. It's a definition.
– Henning Makholm
Jul 15 at 15:27
sorry you're right. would the definition be correct: if x is an element of L, there exists a pi where function V(x, pi) = false
– Lilz
Jul 15 at 16:22