Hamiltonicity proof of knowledge I'm learning the POK notion and definitions and as a self exercise I wante to prove the statement that the Hamiltonicity protocol is a POK system with knowledge error $1/2$.

So the question will be self-contained, I provide here the slide describing the protocol (credits to Moni Naor, Weizmann institute).


  


And the definition as copied from Goldreich's book (Foundation of Cryptography):


  Definition 4.7.3 (system for POK): Let $R$ be a binary relation and $\kappa :N\rightarrow [0,1]$. We say that an interactive function
  $V$ is a knowledge verifier for the relation $R$ with knowledge error
  $\kappa$ if the following two condition holds:
  
  
  Non triviality: There exist an interactive machine $P$ s.t. for every $(x,y)\in R$, all possible interactions of $V$ with $P$ on
  common input $x$ and auxilary input $y$ are accepting.
  Validity: $V$ satisfies the Validity requirement with knowledge error $\kappa$ if there exist a polynimial $q(\cdot )$ s.t. for every
  $P^*$, every $x\in L_R$, there exists a probabilistic oracle machine
  $K$ with oracle access to $P^*$, that run in expected polynomial time
  ad outputs a witness with probability at least $\frac{p-\kappa(|x|)}{q(|x|)}$ where $p$ is the probability that $P^*$ succeeds to
  convince $V$ to accept on common input $x$.
  


My Intuition:

First, it is known that if the commitment scheme is perfectly binding then the above protocol is a IZK proof system with soundness $1/2$.


Non-triviality requirement is trivial to satisfy (specifically, $P$ from the protocol itself satisfies it).
In regard to the Validity requirement, it is easy to construct a Knowledge Extractor


My question:

We know that the soundness of this protocol is $1/2$, so $p\leq 1/2$. Now, it required that there exists a poly $q$ s.t. $K$ succeeds to extract a witness with probability at least $\frac{p-\kappa (|x|)}{q(|x|)}$. If we assigne $p\leq 1/2$ and $\kappa =1/2$, how can such a $q$ exist?
Let $q$ be given by $\:$ for all $n$, $\: q(n) = 1 \;\;$. $\;\;\;\;\;$ For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$,

$\frac{p-\kappa(|x|)}{q(|x|)} = \frac{p-\kappa(|x|)}1 = \:p\hspace{-0.04 in}-\hspace{-0.04 in}\kappa(|x|) \: \leq \: p\hspace{-0.04 in}-\hspace{-0.04 in}0 \: = \: p \: \leq \: 1 \;\;$.

For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$:

Since $\: x\in L_R \:$, $\:$ there exists $y$ such that $\; (x\hspace{.02 in},\hspace{-0.02 in}y)\in R \:\:$. $\;\;\;\;$ Let $w$ be a minimum-length

example of that, and let $K_w$ be the oracle machine that immediately outputs $w$ and then halts.

Since $K_w$ ignores its input and halts, $K_w$ runs in expected polynomial time.

Since $K_w$ outputs $w$ with certainty and $w$ is a witness, $K_w$ outputs a witness with certainty.

In particular, its probability of outputting a witness is at least $\frac{p-\kappa(|x|)}{q(|x|)}$.

Therefore the given Validity condition holds.

Conclusion: $\:$ That book's Validity condition is trivial.