Name
Abstract | ||
|---|---|---|
Given a Boolean propositional formula, φ(Xn) over the basis Ω = {∧, V, ¬}, we consider the following decision problem: is there a subset of literals, S, for which φ(Xn) ≡ ∧y∈Sy or φ(Xn) ≡ Vy∈Sy? We prove that the ‘obvious’ Σ2p upper bound is suboptimal and that the problem is decidable in P|NP the class of languages decidable by polynomial time methods allowed to make non-adaptive queries to an np oracle. We further show that the associated function problem of computing a witnessing such subset when one exists can be solved in FP|NP. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1093/comjnl/bxq050 | Comput. J. |
Keywords | Field | DocType |
non-adaptive query,associated function problem,key words:,boolean propositional formula,languages decidable,polynomial time method,constructing minimal formulae,following decision problem,np oracle,polynomial time,decision problem | Discrete mathematics,Decision problem,Combinatorics,Upper and lower bounds,Oracle,Decidability,Time complexity,Associated function,Propositional formula,Mathematics | Journal |
Volume | Issue | ISSN |
54 | 7 | 0010-4620 |
Citations | PageRank | References |
2 | 0.38 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul E. Dunne | 1 | 1700 | 112.42 |