Complexity of Propositional Proofs Under a Promise
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F10%3A00343940" target="_blank" >RIV/67985840:_____/10:00343940 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Complexity of Propositional Proofs Under a Promise
Popis výsledku v původním jazyce
We study-within the framework of propositional proof complexity-the problem of certifying un-satisfiability of CNF formulas under the promise that any satisfiable formula has many satisfying assignments, where many stands for an explicitly specified function Lambda in the number of variables n. To this end, we develop propositional proof systems under different measures of promises (i. e., different Lambda) as extensions of resolution. This is done by augmenting resolution with axioms that, roughly, caneliminate sets of truth assignments defined by Boolean circuits.
Název v anglickém jazyce
Complexity of Propositional Proofs Under a Promise
Popis výsledku anglicky
We study-within the framework of propositional proof complexity-the problem of certifying un-satisfiability of CNF formulas under the promise that any satisfiable formula has many satisfying assignments, where many stands for an explicitly specified function Lambda in the number of variables n. To this end, we develop propositional proof systems under different measures of promises (i. e., different Lambda) as extensions of resolution. This is done by augmenting resolution with axioms that, roughly, caneliminate sets of truth assignments defined by Boolean circuits.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2010
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
ACM Transactions on Computational Logic
ISSN
1529-3785
e-ISSN
—
Svazek periodika
11
Číslo periodika v rámci svazku
3
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
29
Strana od-do
—
Kód UT WoS článku
000277925300004
EID výsledku v databázi Scopus
—