Cooko–Levino įvykdomumo teorema
Būlio formulių įvykdomumo uždavinys SAT yra NP pilnas pagal polinominio laiko daugelio į vieną redukcijas.
Esminės žinios
Būlio formulių įvykdomumo uždavinys SAT yra NP pilnas pagal polinominio laiko daugelio į vieną redukcijas. Kiekvienai kalbai A∈NP ir įvesčiai x polinominio dydžio formulė koduoja polinominio laiko priimančio skaičiavimo lentelę taip, kad x∈A tada ir tik tada, kai ši formulė yra įvykdoma; pats formulę tenkinantis reikšmių priskyrimas yra NP liudijimas.
Sąlygos ir taikymo ribos
- SAT įvestys yra baigtinės Būlio formulės su tinkamu išreikštiniu kodavimu; redukcija priklauso nuo fiksuoto kalbos A tikrintuvo arba nedeterministinės Tiuringo mašinos (NTM).
- NP pilnumas neįrodo, kad polinominio laiko SAT algoritmo nėra; iš tokio algoritmo egzistavimo išplauktų P=NP.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 16 skaidrės 3–8: Cooko–Levino teoremos formuluotė, lentelės langelių, pradžios, perėjimų ir priėmimo sąlygos, interpretacija abiem kryptimis ir polinominis konstrukcijos dydis.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-cook-levin-sat-completeness
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra