Zobrazeno 1 - 10
of 182
pro vyhledávání: '"Samuel R. Buss"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 10, Issue 2 (2014)
The Stone tautologies are known to have polynomial size resolution refutations and require exponential size regular refutations. We prove that the Stone tautologies also have polynomial size proofs in both pool resolution and the proof system of regu
Externí odkaz:
https://doaj.org/article/ab98e794cdda4823bc92198013ee672e
Publikováno v:
Logical Methods in Computer Science, Vol Volume 4, Issue 4 (2008)
Resolution refinements called w-resolution trees with lemmas (WRTL) and with input lemmas (WRTI) are introduced. Dag-like resolution is equivalent to both WRTL and WRTI when there is no regularity condition. For regular proofs, an exponential separat
Externí odkaz:
https://doaj.org/article/9860ff3ed37349baa9af6375e11ececc
Autor:
Samuel R. Buss
This textbook, first published in 2003, emphasises the fundamentals and the mathematics underlying computer graphics. The minimal prerequisites, a basic knowledge of calculus and vectors plus some programming experience in C or C++, make the book sui
Publikováno v:
ACM Transactions on Computational Logic. 22:1-30
This article is motivated by seeking lower bounds on OBDD(∧, w, r) refutations, namely, OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1 - NBP ∧ refutations based on read-once nondeterministic branching progra
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d3406175cdb55fc4db831856e953c5b0
https://doi.org/10.1145/3468855
https://doi.org/10.1145/3468855
Publikováno v:
Artificial Intelligence
Artificial Intelligence, Elsevier, 2021, 300, pp.1-59. ⟨10.1016/j.artint.2021.103552⟩
Artificial Intelligence, 2021, 300, pp.1-59. ⟨10.1016/j.artint.2021.103552⟩
Artificial Intelligence, Elsevier, 2021, 300, pp.1-59. ⟨10.1016/j.artint.2021.103552⟩
Artificial Intelligence, 2021, 300, pp.1-59. ⟨10.1016/j.artint.2021.103552⟩
International audience; The paper describes the use of dual-rail MaxSAT systems to solve Boolean satisfiability (SAT), namely to determine if a set of clauses is satisfiable. The MaxSAT problem is the problem of satisfying the maximum number of claus
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::06ae2fef8f05cf52cd43ee6681dadd67
https://hal.archives-ouvertes.fr/hal-03317630
https://hal.archives-ouvertes.fr/hal-03317630
Autor:
Samuel R. Buss
Publikováno v:
Outstanding Contributions to Logic ISBN: 9783030714291
We discuss substitution rules that allow the substitution of formulas for formula variables. A substitution rule was first introduced by Frege. More recently, substitution is studied in the setting of propositional logic. We state theorems of Urquhar
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1826ee7f4610e8ad7298e88a78a900f3
https://doi.org/10.1007/978-3-030-71430-7_17
https://doi.org/10.1007/978-3-030-71430-7_17
Autor:
Samuel R. Buss, Arnold Beckmann
Publikováno v:
Annals of Pure and Applied Logic. 170:1176-1187
This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f3c3a02fee0496e8664d10f94307c9b5
https://doi.org/10.1016/j.apal.2019.05.002
https://doi.org/10.1016/j.apal.2019.05.002
Publikováno v:
Recercat. Dipósit de la Recerca de Catalunya
instname
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
instname
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for k-D Tucker for all k ≥ 2 . This corrects a claim in the literature that the Tucker search problem is in PPAD.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dbd97991d685fcf890e257d594b476b2
https://hdl.handle.net/2117/177608
https://hdl.handle.net/2117/177608
Autor:
Ramyaa Ramyaa, Samuel R. Buss
Publikováno v:
Mathematical Logic Quarterly. 64:505-513
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0901420004fafaf4598abbe67849d20b
https://doi.org/10.1002/malq.201700034
https://doi.org/10.1002/malq.201700034
Autor:
Samuel R. Buss
Publikováno v:
Archive for Mathematical Logic. 56:639-669
We give a uniform proof of the theorems of Yao and Beigel–Tarui representing ACC predicates as constant depth circuits with $$\hbox {MOD}_{m}$$ gates and a symmetric gate. The proof is based on a relativized, generalized form of Toda’s theorem ex
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3688ded99f569e63a51a2f770e3e1e7e
https://doi.org/10.1007/s00153-017-0560-9
https://doi.org/10.1007/s00153-017-0560-9