Questions tagged [np]
The np tag has no usage guidance.
5 questions
2
votes
1
answer
157
views
probabilistic polynomial-time Turing machine with one-way function
Suppose that there exists a function $π:\{0,1\}^π β \{0,1\}^π$
such that, π is computable in polynomial time; and the following task cannot be computed in polynomial time (that is, there are $π₯ β ...
- 45
2
votes
2
answers
190
views
How to prove that $𝐿$ is in $\mathsf{NP} \setminus \mathsf{P}?$
Suppose that there exists a function $π:\{0,1\}^π β \{0,1\}^π$
such that, π is computable in polynomial time; and the following task cannot be computed in polynomial time (that is, there are $π₯ β ...
- 45
1
vote
3
answers
494
views
P versus semi-NP?
I am not sure to fully understand the interest of the P versus NP problem for cryptography. I get that it is important to have a problem which is hard to solve but easy to check. But it seems to me ...
- 113
2
votes
1
answer
77
views
3-Coloring Zero-Knowledge Proof: rational verifier?
I'm studying the application of Zero-Knowledge Proofs (ZKP) to graph 3-colorability. I haven't fully understood the need for randomness in the verifier's choice of the edge to challenge the prover ...
- 23
0
votes
0
answers
49
views
One-way function constructed by multivariable polynomials
Although the conjecture regarding the existence of one-way functions remained open, there are numerous NP-based methods for constructing diverse one-way functions, including DL, lattice, and subset ...
- 456