imported>Citation bot: Altered journal. Added bibcode. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2025-12-21T02:32:50Z

Altered journal. Added bibcode. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 02:32, 21 December 2025
Line 37:		Line 37:
	{{Main\|Cook–Levin theorem}}		{{Main\|Cook–Levin theorem}}

	SAT was the first problem known to be [[NP-complete]], as proved by [[Stephen Cook]] at the [[University of Toronto]] in 1971<ref>{{Cite book \| last1 = Cook \| first1 = Stephen A. \| title = Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 \| chapter = The complexity of theorem-proving procedures \| author-link1=Stephen Cook\| pages = 151–158 \| year = 1971 \| chapter-url=http://www.cs.toronto.edu/~sacook/homepage/1971.pdf \|archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.toronto.edu/~sacook/homepage/1971.pdf \|archive-date=2022-10-09 \|url-status=live\| doi = 10.1145/800157.805047\| citeseerx = 10.1.1.406.395 \| s2cid = 7573663 }}</ref> and independently by [[Leonid Levin]] at the [[Russian Academy of Sciences#The Academy of Sciences of the USSR\|Russian Academy of Sciences]] in 1973.<ref>{{cite journal\|last=Levin\|first=Leonid\|author-link=Leonid Levin\|title = Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)\|journal = Problems of Information Transmission (Russian: Проблемы ~~передачи информа́ции~~, Problemy Peredachi Informatsii)\|volume = 9\|issue = 3\|pages = 115–116\|year = 1973}} [http://www.mathnet.ru/php/getFT.phtml?jrnid=ppi&paperid=914&volume=9&year=1973&issue=3&fpage=115&what=fullt&option_lang=eng (pdf)] {{in lang\|ru}}, translated into English by {{cite journal\|last=Trakhtenbrot\|first=B. A.\|title = A survey of Russian approaches to ''perebor'' (brute-force searches) algorithms\|journal = Annals of the History of Computing \|volume = 6\|issue = 4\|pages = 384–400\|year = 1984\|doi=10.1109/MAHC.1984.10036\|s2cid=950581}}</ref> Until that time, the concept of an NP-complete problem did not even exist. The proof shows how every decision problem in the [[complexity class]] [[NP (complexity)\|NP]] can be [[reduction (complexity)\|reduced]] to the SAT problem for CNF{{efn\|The SAT problem for ''arbitrary'' formulas is NP-complete, too, since it is easily shown to be in NP, and it cannot be easier than SAT for CNF formulas.}} formulas, sometimes called '''CNFSAT'''. A useful property of Cook's reduction is that it preserves the number of accepting answers. For example, deciding whether a given [[Graph (discrete mathematics)\|graph]] has a [[Graph coloring#Vertex coloring\|3-coloring]] is another problem in NP; if a graph has 17 valid 3-colorings, then the SAT formula produced by the Cook–Levin reduction will have 17 satisfying assignments.		SAT was the first problem known to be [[NP-complete]], as proved by [[Stephen Cook]] at the [[University of Toronto]] in 1971<ref>{{Cite book \| last1 = Cook \| first1 = Stephen A. \| title = Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 \| chapter = The complexity of theorem-proving procedures \| author-link1=Stephen Cook\| pages = 151–158 \| year = 1971 \| chapter-url=http://www.cs.toronto.edu/~sacook/homepage/1971.pdf \|archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.toronto.edu/~sacook/homepage/1971.pdf \|archive-date=2022-10-09 \|url-status=live\| doi = 10.1145/800157.805047\| citeseerx = 10.1.1.406.395 \| s2cid = 7573663 }}</ref> and independently by [[Leonid Levin]] at the [[Russian Academy of Sciences#The Academy of Sciences of the USSR\|Russian Academy of Sciences]] in 1973.<ref>{{cite journal\|last=Levin\|first=Leonid\|author-link=Leonid Levin\|title = Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)\|journal = Problems of Information Transmission (Russian: Проблемы Передачи Информа́ции, Problemy Peredachi Informatsii)\|volume = 9\|issue = 3\|pages = 115–116\|year = 1973}} [http://www.mathnet.ru/php/getFT.phtml?jrnid=ppi&paperid=914&volume=9&year=1973&issue=3&fpage=115&what=fullt&option_lang=eng (pdf)] {{in lang\|ru}}, translated into English by {{cite journal\|last=Trakhtenbrot\|first=B. A.\|title = A survey of Russian approaches to ''perebor'' (brute-force searches) algorithms\|journal = Annals of the History of Computing \|volume = 6\|issue = 4\|pages = 384–400\|year = 1984\|doi=10.1109/MAHC.1984.10036\|bibcode=1984IAHC....6d.384T \|s2cid=950581}}</ref> Until that time, the concept of an NP-complete problem did not even exist. The proof shows how every decision problem in the [[complexity class]] [[NP (complexity)\|NP]] can be [[reduction (complexity)\|reduced]] to the SAT problem for CNF{{efn\|The SAT problem for ''arbitrary'' formulas is NP-complete, too, since it is easily shown to be in NP, and it cannot be easier than SAT for CNF formulas.}} formulas, sometimes called '''CNFSAT'''. A useful property of Cook's reduction is that it preserves the number of accepting answers. For example, deciding whether a given [[Graph (discrete mathematics)\|graph]] has a [[Graph coloring#Vertex coloring\|3-coloring]] is another problem in NP; if a graph has 17 valid 3-colorings, then the SAT formula produced by the Cook–Levin reduction will have 17 satisfying assignments.

	NP-completeness only refers to the run-time of the worst case instances. Many of the instances that occur in practical applications can be solved much more quickly. See [[#Algorithms for solving SAT\|§Algorithms for solving SAT]] below.		NP-completeness only refers to the run-time of the worst case instances. Many of the instances that occur in practical applications can be solved much more quickly. See [[#Algorithms for solving SAT\|§Algorithms for solving SAT]] below.

imported>Elestrophe: Fix meaning of sentence since the listed fields are not themselves SAT problems.

2025-11-05T02:49:36Z

Fix meaning of sentence since the listed fields are not themselves SAT problems.

Show changes

imported>Caleb Stanford: minor c/e

2025-06-24T16:46:31Z

minor c/e

Show changes

imported>Giftlite: /* Algorithms for solving SAT */ wlnk

2025-06-16T16:19:04Z

Algorithms for solving SAT: wlnk

Show changes

imported>Ftiercel: /* XOR-satisfiability */ Examples

2025-05-30T16:31:33Z

XOR-satisfiability: Examples

Show changes

← Previous revision		Revision as of 02:32, 21 December 2025
Line 37:		Line 37:
	{{Main\|Cook–Levin theorem}}		{{Main\|Cook–Levin theorem}}

	SAT was the first problem known to be [[NP-complete]], as proved by [[Stephen Cook]] at the [[University of Toronto]] in 1971<ref>{{Cite book \| last1 = Cook \| first1 = Stephen A. \| title = Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 \| chapter = The complexity of theorem-proving procedures \| author-link1=Stephen Cook\| pages = 151–158 \| year = 1971 \| chapter-url=http://www.cs.toronto.edu/~sacook/homepage/1971.pdf \|archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.toronto.edu/~sacook/homepage/1971.pdf \|archive-date=2022-10-09 \|url-status=live\| doi = 10.1145/800157.805047\| citeseerx = 10.1.1.406.395 \| s2cid = 7573663 }}</ref> and independently by [[Leonid Levin]] at the [[Russian Academy of Sciences#The Academy of Sciences of the USSR\|Russian Academy of Sciences]] in 1973.<ref>{{cite journal\|last=Levin\|first=Leonid\|author-link=Leonid Levin\|title = Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)\|journal = Problems of Information Transmission (Russian: Проблемы ~~передачи информа́ции~~, Problemy Peredachi Informatsii)\|volume = 9\|issue = 3\|pages = 115–116\|year = 1973}} [http://www.mathnet.ru/php/getFT.phtml?jrnid=ppi&paperid=914&volume=9&year=1973&issue=3&fpage=115&what=fullt&option_lang=eng (pdf)] {{in lang\|ru}}, translated into English by {{cite journal\|last=Trakhtenbrot\|first=B. A.\|title = A survey of Russian approaches to ''perebor'' (brute-force searches) algorithms\|journal = Annals of the History of Computing \|volume = 6\|issue = 4\|pages = 384–400\|year = 1984\|doi=10.1109/MAHC.1984.10036\|s2cid=950581}}</ref> Until that time, the concept of an NP-complete problem did not even exist. The proof shows how every decision problem in the [[complexity class]] [[NP (complexity)\|NP]] can be [[reduction (complexity)\|reduced]] to the SAT problem for CNF{{efn\|The SAT problem for ''arbitrary'' formulas is NP-complete, too, since it is easily shown to be in NP, and it cannot be easier than SAT for CNF formulas.}} formulas, sometimes called '''CNFSAT'''. A useful property of Cook's reduction is that it preserves the number of accepting answers. For example, deciding whether a given [[Graph (discrete mathematics)\|graph]] has a [[Graph coloring#Vertex coloring\|3-coloring]] is another problem in NP; if a graph has 17 valid 3-colorings, then the SAT formula produced by the Cook–Levin reduction will have 17 satisfying assignments.		SAT was the first problem known to be [[NP-complete]], as proved by [[Stephen Cook]] at the [[University of Toronto]] in 1971<ref>{{Cite book \| last1 = Cook \| first1 = Stephen A. \| title = Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 \| chapter = The complexity of theorem-proving procedures \| author-link1=Stephen Cook\| pages = 151–158 \| year = 1971 \| chapter-url=http://www.cs.toronto.edu/~sacook/homepage/1971.pdf \|archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.toronto.edu/~sacook/homepage/1971.pdf \|archive-date=2022-10-09 \|url-status=live\| doi = 10.1145/800157.805047\| citeseerx = 10.1.1.406.395 \| s2cid = 7573663 }}</ref> and independently by [[Leonid Levin]] at the [[Russian Academy of Sciences#The Academy of Sciences of the USSR\|Russian Academy of Sciences]] in 1973.<ref>{{cite journal\|last=Levin\|first=Leonid\|author-link=Leonid Levin\|title = Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)\|journal = Problems of Information Transmission (Russian: Проблемы Передачи Информа́ции, Problemy Peredachi Informatsii)\|volume = 9\|issue = 3\|pages = 115–116\|year = 1973}} [http://www.mathnet.ru/php/getFT.phtml?jrnid=ppi&paperid=914&volume=9&year=1973&issue=3&fpage=115&what=fullt&option_lang=eng (pdf)] {{in lang\|ru}}, translated into English by {{cite journal\|last=Trakhtenbrot\|first=B. A.\|title = A survey of Russian approaches to ''perebor'' (brute-force searches) algorithms\|journal = Annals of the History of Computing \|volume = 6\|issue = 4\|pages = 384–400\|year = 1984\|doi=10.1109/MAHC.1984.10036\|bibcode=1984IAHC....6d.384T \|s2cid=950581}}</ref> Until that time, the concept of an NP-complete problem did not even exist. The proof shows how every decision problem in the [[complexity class]] [[NP (complexity)\|NP]] can be [[reduction (complexity)\|reduced]] to the SAT problem for CNF{{efn\|The SAT problem for ''arbitrary'' formulas is NP-complete, too, since it is easily shown to be in NP, and it cannot be easier than SAT for CNF formulas.}} formulas, sometimes called '''CNFSAT'''. A useful property of Cook's reduction is that it preserves the number of accepting answers. For example, deciding whether a given [[Graph (discrete mathematics)\|graph]] has a [[Graph coloring#Vertex coloring\|3-coloring]] is another problem in NP; if a graph has 17 valid 3-colorings, then the SAT formula produced by the Cook–Levin reduction will have 17 satisfying assignments.

	NP-completeness only refers to the run-time of the worst case instances. Many of the instances that occur in practical applications can be solved much more quickly. See [[#Algorithms for solving SAT\|§Algorithms for solving SAT]] below.		NP-completeness only refers to the run-time of the worst case instances. Many of the instances that occur in practical applications can be solved much more quickly. See [[#Algorithms for solving SAT\|§Algorithms for solving SAT]] below.

Boolean satisfiability problem - Revision history

imported>Citation bot: Altered journal. Added bibcode. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

imported>Elestrophe: Fix meaning of sentence since the listed fields are not themselves SAT problems.

imported>Caleb Stanford: minor c/e

imported>Giftlite: /* Algorithms for solving SAT */ wlnk

imported>Ftiercel: /* XOR-satisfiability */ Examples