Michael Hersche, Mustafa Zeqiri, et al.
NeSy 2023
We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof. We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.
Michael Hersche, Mustafa Zeqiri, et al.
NeSy 2023
Khalid Abdulla, Andrew Wirth, et al.
ICIAfS 2014
Benjamin N. Grosof
AAAI-SS 1993
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence