Solving Q SAT in bounded space and time by geometrical computation

Denys Duchier

Description

Solving Q-SAT in bounded space and time by geometrical computation Solving Q-SAT in bounded space and time by geometrical computation Denys Duchier 1 , Jérôme Durand-Lose 2 , Maxime Senot 2 1 Team Constraint & Machine Learning 2 Team Graphs & Algorithms Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, Orléans, FRANCE Partially supported by the ANR AGAPE, ANR-09-BLAN-0159-03. CiE '11, Sofia, Bulgaria 28th June 2011 1 / 41

• recursive algorithm


• bounded space


• decision problem


• false ?


• team graphs


• laboratoire d'informatique fondamentale d'orléans


• brute force

Sujets

• Recursion (computer science)
• Metric space
• Decision problem
• Brute Force

Informations

• Publié par: pefav
• Nombre de lectures: 32
• Langue: English

Extrait

oSolving0Q-SAsuppT&ind'Orl?ans,bGAPE,oundedhspacemandFRANCEtimeyb0ySogeome1triricalscomputationd'InfoSolvingFQ-SAd'Orl?ans,TainrtedbANRoundedNspaceNandCiEtimeBulgabJuney41geometricalAlgocomputtmationLabDenysratoireDuchierr1atique,ondamentaleJ?r?meUniversit?Durand-LoseOrl?ans,2P,rtiallyMaximeoSenotb2the1ATAeaR-m9-BLAConstraint-&159-03.Machine'11,Leaa,rningria228thT2011ea/mGraphs1Solving4Q-SASignalT41inTb3ounde2dcomputationspaceQ-SAand2timemachinesbImplantationyConclusiongeome/tricalQ-SASolving3Q-SATT3in1bSignalounde4d41spaceTandQ-SAtime2bmachinesyImplantationgeomeConclusiont/ricalcomputationφ
φ
φ =∃ ∀ ∀ ∧(¬ ∨ )
mogeomedt2ricaliscomputationofQ-SAxTckmeyQ-SA-complete.TwithDecision4pxroblemandQ-SA2TQ-SAInputA:ouraofquantiedusualbyoxoleantimefo3rmula1bspacexxyremb3.TheoQuestion[Sto:er,1973]IsTinPSPtrueCEoOnrclassicalfalse?delExamplecomputationTtheQ-SAnotionSolvingcomplexit41.1/oundex(∃ ψ) = (ψ[ ← ])∨ (ψ[ ← ])
(∀ ψ) = (ψ[ ← ])∧ (ψ[ ← ])
(β) = (β) β

(∀ ∀ ∧(¬ ∨ ))
(∃ ∀ ∀ ∧(¬ ∨ ))=∨
(∀ ∀ ∧(¬ ∨ ))
(∀ ∧(¬ ∨ ))∧
(∀ ∧(¬ ∨ ))=∨
(∀ ∧(¬ ∨ ))∧
(∀ ∧(¬ ∨ ))
=...
V2xgeomexxtrue3groundxx1xyxb3time3xBrute2RecursivetruetruexV3trueVPxoleanandoVaspaceQ-SAdfalsextrue2rceoundealgoxtrue3falsefalsexbxinfalseTxxolynomial2rmula.Q-SAfoxx3falseSolvingbVfalsetxxisV/if231Txfo3evaltrue3xsolutionricalVcomputationVx32rithmVVxx33ExampleVtimexonential3expVbutVefalsec3aspV5x41x∃
∀ ∀
∀ ∀ ∀ ∀
=
ψ( , , )
φ =∃ ∀ ∀ ψ( , , ) ψ = ∧(¬ ∨ )
23txx3xtimePt3inyxscheme33T1xQ-SA2whereQ-SA1xx31Solvingxxrallelistationx/aandxbTx22xtcomputationxricaltxoundegeome1bx2dspace3t6x413∃
==
∀ ∀
∀ ∀ ∀ ∀
=
ψ( , , )
φ =∃ ∀ ∀ ψ( , , ) ψ = ∧(¬ ∨ )
space3xy3tricaloundexx13Q-SAxtrue1xbandfalserallelistationinxxT2xTSolvingxx31Q-SA1xx2/xbschemexxxa32Pt3dwheretcomputation21xt1time23xgeomet7x413∃
==
∀ ∀
= == =
∀ ∀ ∀ ∀
= = = == = = =
ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , )
φ =∃ ∀ ∀ ψ( , , ) ψ = ∧(¬ ∨ )
ftxcomputationtruetaricalxx13xtxtschemext2truegeomextrue2xx13y3falsefbtx322time1x13xand2fxtxttf3ftfffxxin3rallelistationspacetftftfxtTxxfQ-SA3xtSolvingffQ-SAxxT3x2fx33false21oundexfalse2b3xwhere33P1fxt/2dxtx8x413∃
∀ ∀
∀ ∀ ∀ ∀
ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , )
φ =∃ ∀ ∀ ψ( , , ) ψ = ∧(¬ ∨ )
xftdschemet1oundePtfbxfalsetin2xx2falseTgeomex33falseQ-SAxfalse3tTfxfaxrallelistationf21ytruet3txtttruexricalfx2computationand2xxspaceQ-SAf411xx3ffalse3timewheretfalsef1tfbxftt3f9/trueSolving∃
∀ ∀
∧ ∧ ∧ ∧
ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , ) ψ( , , )
φ =∃ ∀ ∀ ψ( , , ) ψ = ∧(¬ ∨ )
Tt1oundeffalsefalsebrallelistationxt2ricalin2TxQ-SAb41yfffxfalse3fQ-SAfxtruefxff2tt1tftruexgeometx2ttrue2txxcomputationdx1/xspacett3fwherefPand1falseatimexfalsetSolving3false10schemett