Filtyp
We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size nω(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size nO(ω) is essentially tight. Moreover, our lower bounds can be generalized to polynomial calculus resolution (PCR) and Sherali-Adams, implying tha
During the last decade, an active line of research in proof complexity has been into the space complexity of proofs and how space is related to other measures. By now these aspects of resolution are fairly well understood, but many open problems remain for the related but stronger polynomial calculus (PC/PCR) proof system. For instance, the space complexity of many standard "benchmark formulas" is
We present size-space trade-offs for the polynomial calculus (PC) and polynomial calculus resolution (PCR) proof systems. These are the first true size-space trade-offs in any algebraic proof system, showing that size and space cannot be simultaneously optimized in these models. We achieve this by extending essentially all known size-space trade-offs for resolution to PC and PCR. As such, our resu
Pebble games were extensively studied in the 1970s and 1980s in a number of different contexts. The last decade has seen a revival of interest in pebble games coming from the field of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space tr
Boolean satisfiability (SAT) solvers have improved enormously in performance over the last 10-15 years and are today an indispensable tool for solving a wide range of computational problems. However, our understanding of what makes SAT instances hard or easy in practice is still quite limited. A recent line of research in proof complexity has studied theoretical complexity measures such as length,
During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving. For the polynomial calculus proof system, the only previously known space lower bound is for CNF formulas of unbounded width in [Alekhnovich
An active line of research in proof complexity over the last decade has been the study of proof space and trade-offs between size and space. Such questions were originally motivated by practical SAT solving, but have also led to the development of new theoretical concepts in proof complexity of intrinsic interest and to results establishing nontrivial relations between space and other proof comple
The last decade has seen a revival of interest in pebble games in the context of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. The typical approach has been to encode the pebble game played on a graph as a CNF formula an
A well-known theorem by Tarsi states that a minimally unsatisfiable CNF formula with m clauses can have at most m - 1 variables, and this bound is exact. In the context of proving lower bounds on proof space in k-DNF resolution, [Ben-Sasson and Nordström 2009] extended the concept of minimal unsatisfiability to sets of k-DNF formulas and proved that a minimally unsatisfiable k-DNF set with m formu
The last decade has seen a revival of interest in pebble games in the context of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. The typical approach has been to encode the pebble game played on a graph as a CNF formula an
We present a greatly simplified proof of the length-space trade-off result for resolution in [P. Hertel, T. Pitassi, Exponential time/space speedups for resolution and the PSPACE-completeness of black-white pebbling, in: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS '07), Oct. 2007, pp. 137-149], and also prove a couple of other theorems in the same vein. W
The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of clauses kept in memory simultaneously if the proof is only allowed to infer new clauses from clauses currently in memory. Both of these measures have previously been studied and related to the resolution refutation size of unsatisfiable conjunctive normal form
A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space. In this paper we resolve the question by answering it negatively in the strongest possible way. We show that there are families of 6-CNF formulas of size n, fo
Most state-of-the-art satisfiability algorithms today are variants of the DPLL procedure augmented with clause learning. The main bottleneck for such algorithms, other than the obvious one of time, is the amount of memory used, fn the field of proof complexity, the resources of time and memory correspond to the length and space of resolution proofs. There has been a long line of research trying to
The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of clauses kept in memory simultaneously if the proof is only allowed to infer new clauses from clauses currently in memory. Both of these measures have previously been studied and related to the resolution refutation size of unsatisfiable CNF formulas. Also, the
Background. Efforts to identify specific variables that impact most on outcomes from interdisciplinary pain rehabilitation are challenged by the complexity of chronic pain. Methods to manage this complexity are needed. The purpose of the study was to determine the network structure entailed in a set of self-reported variables, examine change, and look at potential predictors of outcome, from a net
2011 är ett viktigt år för den svenska gymnasieutbildningen. Genom en omfattande gymnasiereform, förkortad GY11, sjösattes den nya gymnasieskolan. Genom GY11 skulle yrkesutbildningarna lägga större betoning på yrkesämnena, ha karaktären av färdigutbildning, avslutas med en yrkesexamen samt bli mer avnämarstyrda och präglade av arbetslivets behov. Förhoppningen var att yrkesutbildningarna skulle bl
I det inledande kapitlet av antologin motiveras fokus i boken såväl som yrkesutbildningens attraktionskraft lyfts fram i siffror. Därutöver diskuteras betydelsen av att uppmärksamma yrkesutbildningens attraktionskraft. Det inledande kapitlet avslutas med en presentation av bokens disposition.
Syftet med detta kapitel är att förklara yrkesutbildningens låga attraktionskraft genom att illustrera framväxten av det utbildnings-politiska paradigm som lagt grunden för den svenska utbildningspolitikens ideologiska grundvalar. Detta görs genom att studera utbildningspolitiska texter samt analysera föreställningar om yrkesutbildningar bland utbildningsforskare och skolrepresentanter på kommunal
I detta kapitel undersöks yrkesutbildningens attraktionskraft sett ur högstadieelevers perspektiv. Kapitlet omfattar tre rubriker. Under den första diskuteras den använda metoden för empiriinsamling samt urvalet av kommuner. Därefter redovisas det empiriska materialet under en separat rubrik som svarar på antologins första fråga (Vad vet vi om den gymnasiala yrkesutbildningens attraktionskraft?) u
