Abstrakt. Vi bevisar att för oändligt många disjunktiv normal form propositional calculus tautologies ~:, längden på den kortaste upplösningen bevis på ~: kan inte begränsas av någon polynom av längden på ~=. De tautologier vi använder introducerades av Cook och Reckhow (1979) och kodade duvhålsprincipen. Utökad upplösning kan ge polynom långa bevis på dessa formler. Definitioner och bakgrundsteorem som visar med hjälp av upplösning infördes av Robinson [8]. Metoden är tillämplig på första ordningen predicate calculus eller på proteal calculus. Om den formel som ska bevisas är en följd av axiom, är upplösning används för att bevisa diskontering av den ursprungliga formeln med negations av dessa axioms den beror på. Predicate calculus formler reduceras till proportional calculus formler genom att använda kvantifier eliminering tekniker. Dessutom sätts den formel som ska bevisas i disjunktiv normal form (DNF). Teoremet som bevisar uppgiften reduceras sedan till att bevisa att en given DNF propositionell kalkyl formel är en tautologi. För att visa icke-polynomisk komplexitet, anser vi endast DNF propositionella kalkylformler. Vi använder notationen '+' för logiska 'eller', juxtaposition för 'och', och '" för negation (x' är 'inte x'). Ett exempel på en DNF propositionell tautologi är: abc'+ ab'd + ab' c'd' + a'd + a' c'd' + c. För att definiera upplösningen låter vi s r vara en DNF propositional calculus tautology, och vi beskriver hur upplösning producerar ett bevis på s r. Sambanden av vilka ~ är en disjunktion kallas klausuler och ~: anses vara en uppsättning klausuler. Variablerna och de negativa variabler av vilka en klausul är en förening kallas bokstavliga. En klausul anses vara en uppsättning ordagrants ~ En klausul täcker en sanning uppdrag till variablerna i ~: om sanningen uppdrag gör klausulen sant. Resolutionsförfarandet visar ~ vara en tautologi genom att visa att varje sanningstilldelning omfattas av någon klausul i s r. Förfarandet börjar med den ursprungliga uppsättningen klausuler i s r och genererar upprepade gånger nya klausuler från befintliga. Varje ny klausul härrör från två tidigare befintliga klausuler och den nya omfattar endast sanningsuppdrag 0304-3975/85/$3.30 © 1985, Elsevier Science Publishers B.V. (North-Holland)
Ett seminalt resultat är att en propositionell kodning av duvhålsprincipen inte har några polynomiska upplösningsbevis REF ].
The intractability of resolution
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}