Skip to main content
added 40 characters in body
Source Link
xskxzr
  • 7.6k
  • 5
  • 23
  • 47

A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\{ w \space | V \space accepts \space <w,c> \space for \space some \space string \space c\right\}$$$$A=\left\{ w \space | V \space \text{accepts} \space \langle w,c\rangle \space\text{for}\space \text{some} \space \text{string} \space c\right\}.$$

My question about this definition is what is this string $c$ stands for?

Let's say I have a graph and I want to verify if it has a clique. What would be my $c$?

A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\{ w \space | V \space accepts \space <w,c> \space for \space some \space string \space c\right\}$$

My question about this definition is what is this string $c$ stands for?

Let's say I have a graph and I want to verify if it has a clique. What would be my $c$?

A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\{ w \space | V \space \text{accepts} \space \langle w,c\rangle \space\text{for}\space \text{some} \space \text{string} \space c\right\}.$$

My question about this definition is what is this string $c$ stands for?

Let's say I have a graph and I want to verify if it has a clique. What would be my $c$?

edited title
Link
Alan
  • 315
  • 3
  • 8

Verifier - Complexity Theory

Source Link
Alan
  • 315
  • 3
  • 8

Verifier Complexity Theory

A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\{ w \space | V \space accepts \space <w,c> \space for \space some \space string \space c\right\}$$

My question about this definition is what is this string $c$ stands for?

Let's say I have a graph and I want to verify if it has a clique. What would be my $c$?