Sökresultat

Popular Abstract in Swedish Kan vårdbehov mätas? Under de senaste decennierna har studier från olika delar av västvärlden kunnat visa att det finns skillnader mellan olika sociala klasser i sjukdomsförekomst och förtidig död. Sådana skillnader finns även i Sverige, trots att politikerna sedan länge satsat på utjämning av klasskillnader och vård på lika villkor för alla. Den ekonomiska tillväxten Aims: To analyse the associations between health and neighbourhood social position, measured by a composite index (Care Need Index, CNI). Furthermore evaluate CNI in preparation for future analysis of its usefulness for allocating primary health care resources to deprived neighbourhoods. Methods: One fourth of the Swedish general practitioners ranked the impact of eight different variables: elder

This paper presents a design study aiming to compare a PMSM, EMSM and an SMSM solution in order to rind the most competitive one for the BAS application. The study is mainly based on FE calculations, which are contrasted with the results obtained from a common car alternator. The highlights are efficiency and torque characteristics, and the way they contribute to improve the most important feature

The unison songs has united people about common goals and experiences in the three great folk movements in Sweden, the Revivalist movement, the Temperance movement and the Socialist movement, especially during the most expansive period, 1850-1920. The aim/purpose of my investigation has been to examine how the different ideolgies are breaking against each other in the songs published for unison so

No Trouble Found (NTF) has been discussed for several years [1]. An NTF occurs when a device fails at the board/system level and that failure cannot be confirm by the component supplier. There are several explanations for why NTFs occur, including: device complexity; inability to create system level hardware/software transactions which uncover hard to find defects; different environments during te

Popular AbstractDen här avhandlingen handlar om enpartistatens kollaps i Ungern och övergången till parlamentarisk demokrati i slutet av 1980- och början av 90-talet. Denna process, fortsättningsvis kallad transitionsprocessen, medförde förändringar inte bara i den politiska toppen, utan hade också återverkningar på de intellektuella och ekonomiska fälten. Drivkraften bakom dessa förändringar var,This dissertation explains the transition - the change of political system from a one-party state to a multi-party system - in Hungary as the result of a generation change, where different generations with different historical experiences either lost or gained political capital. It also includes a review of what consequences the changes in the political field had for the intellectual and economic

We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games. We prove that the problem of deciding whether s pebbles suffice to reversibly pebble a DAG G is PSPACE-comple

We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov'03] established that if the clause-variable incidence graph of a CNF formula F is a good enough expander, then proving that F is unsatisfiable requires high PC/PCR degree. We further

We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size nΩ(d) for values of d = d(n) from constant all the way up to nδ for some universal constant δ. This shows that the nO(d) running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs

In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of a Conjunctive Normal Form (CNF) formula is always an upper bound on the width needed to refute the formula. Their proof is beautiful but uses a nonconstructive argument based on Ehrenfeucht-Fraïssé games. We give an alternative, more explicit, proof that works

During the last 10 to 15 years, 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 concern in SAT solving, and so research has mostly focused on weak systems that are used by SAT solvers. There has been a relatively long sequence of paper

In 2010, Spence and Van Gelder presented a family of CNF formulas based on combinatorial block designs. They showed empirically that this construction yielded small instances that were orders of magnitude harder for state-of-the-art SAT solvers than other benchmarks of comparable size, but left open the problem of proving theoretical lower bounds. We establish that these formulas are exponentially

This talk is intended as a selective survey of proof complexity, focusing on some comparatively weak proof systems that are of particular interest in connection with SAT solving. We will review resolution, polynomial calculus, and cutting planes (related to conflict-driven clause learning, Gröbner basis computations, and pseudo-Boolean solvers, respectively) and some proof complexity measures that

In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of formulas is always an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies heavily on tools from finite model theory. We give an alternative, completely elementary, proof that works by simple syntact

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