Karp–Lipton theorem
id:
karp-lipton-theorem-272-5484327
title:
Karp–Lipton theorem
text:
In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then That is, if we assume that NP, the class of nondeterministic polynomial time problems, can be contained in the non-uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the polynomial hierarchy at its second level. Such a collapse is believed unlikely, so the theorem is general
brand slug:
wiki
category slug:
encyclopedia
description:
On collapse of the polynomial hierarchy if NP is in non-uniform polynomial time class
original url:
https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem
date created:
date modified:
2024-04-02T18:28:30Z
main entity:
{"identifier":"Q6373327","url":"https://www.wikidata.org/entity/Q6373327"}
image:
fields total:
13
integrity:
14