Complexity of Propositional Proofs Under a Promise

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Complexity of Propositional Proofs Under a Promise

Original language description

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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2010

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

ACM Transactions on Computational Logic

ISSN

1529-3785

e-ISSN

—

Volume of the periodical

11

Issue of the periodical within the volume

3

Country of publishing house

US - UNITED STATES

Number of pages

29

Pages from-to

—

UT code for WoS article

000277925300004

EID of the result in the Scopus database

—