Sökning: "Beviskomplexitet"
Hittade 2 avhandlingar innehållade ordet Beviskomplexitet.
1. Short Proofs May Be Spacious : Understanding Space in Resolution
Sammanfattning : Om man ser på de bästa nu kända algoritmerna för att avgöra satisfierbarhet hos logiska formler så är de allra flesta baserade på den så kallade DPLL-metoden utökad med klausulinlärning. De två viktigaste gränssättande faktorerna för sådana algoritmer är hur mycket tid och minne de använder, och att förstå sig på detta är därför en fråga som har stor praktisk betydelse. LÄS MER
2. On Long Proofs of Simple Truths
Sammanfattning : Propositional proof complexity is the study of certificates of infeasibility. In this thesis we consider several proof systems with limited deductive ability and unconditionally show that they require long refutations of the feasibility of certain Boolean formulas. LÄS MER