Article citationsMore>>

Goldreich, O. (2010) P, NP, and NP-Completeness: The Basics of Computational Complexity. Cambridge University Press.
https://doi.org/10.1017/CBO9780511761355

has been cited by the following article:

• TITLE: Quantum Algorithm for Solving Tautology and Satisfiability Problems

  AUTHORS: Amrita Mitra

  KEYWORDS: Quantum Algorithm, Tautology Problem, Satisfiability Problem, NP-Completeness, Co-NP-Completeness

  JOURNAL NAME: Journal of Quantum Information Science, Vol.16 No.1, March 13, 2026

  ABSTRACT: This paper proposes a quantum algorithm for solving the tautology and the satisfiability problems for a Boolean formula. Let’s say we are given a Boolean formula. The variables of the Boolean formula can take only two values—TRUE or FALSE. The tautology problem asks whether the Boolean formula always evaluates to TRUE for all values of its Boolean variables. The satisfiability problem asks whether the Boolean formula can evaluate to TRUE for at least one set of values of its Boolean variables. This paper proposes that both problems can be solved using the proposed quantum algorithm. The tautology problem is known to be co-NP-complete. The satisfiability problem is known to be NP-complete.