Įvykdomumą išsauganti SAT redukcija į 3SAT
Įvesti kintamuosius Būlio poformulių loginiams elementams, ne daugiau kaip trijų literalų disjunkcijomis užtikrinti, kad kiekvieno elemento reikšmė atitiktų jo įvestis, ir reikalauti, kad išvesties elemento reikšmė būtų tiesa.
Esminės žinios
Įveskite kintamuosius Bulio subformulių loginiams elementams, ne daugiau kaip trijų literalų klauzulėmis užtikrinkite, kad kiekvieno loginio elemento reikšmė atitiktų jo įėjimus, ir reikalaukite, kad išėjimo loginio elemento reikšmė būtų teisinga. Taip sudaroma tiesinio dydžio 3CNF formulė, tenkinama tada ir tik tada, kai tenkinama pradinė formulė; tai parodo, kad SAT≤ₚ3SAT, taigi 3SAT yra NP-pilnas.
Sąlygos ir taikymo ribos
- Pradinės formulės sintaksės medis turi aiškią koduotę; nauji kintamieji nesutampa su jau esančiais, o jų reikšmes galima parinkti egzistenciškai.
- Vienodas tenkinamumas nėra formulių ekvivalentiškumas išplėstoje kintamųjų aibėje. Vieno ar dviejų literalų klauzules galima papildyti kartojant literalus, jei reikalaujama lygiai trijų pozicijų.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 16 skaidrėje 9 pateikta loginių elementų ir subformulių konstrukcija bei 3SAT teorema. Loginių elementų ekvivalentiškumui naudojamos abi implikacijos kryptis aprašančios tiesos lentelės klauzulės; papildant kartojamas literalas, nekeičiant klauzulės reikšmės.
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-sat-three-cnf-reduction
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra