Computational Complexity and Fixpoint Logics Relationship
Delve into the intricate connection between computational complexity and fixpoint logics as explored in the seminal work by Abiteboul, Vardi, and Vianu. From overcoming fundamental mismatches to defining relational complexity classes, this research sheds light on the interplay between logic and complexity theory, offering insights into the relationships among PTIME, EXPTIME, NP, PSPACE, fixpoint logics, and more.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Fixpoint Logics, Relational Machines, and Computational Complexity Serge Abiteboul, Moshe Vardi, Victor Vianu JACM 1997
Starting point Fixpoint + < = PTIME [Vardi, Immerman] Basic mismatch between logic and complexity logic 011000111010010 <
Overcoming the mismatch: relational machine Similar in spirit to embedded SQL logic FO FO
Relational complexity Class (resource, control, bound) r Measure of input: not the actual size Defined relative to the discerning power of the machine
Relational complexity EXPTIME EXPTIME r PSPACE PSPACE r NP NP r P P r
Relational complexity EXPTIME EXPTIME r PSPACE PSPACE r NP NP r P P = fixpoint r
Variants of fixpoint logics FP(control, (non)-inflationary) Deterministic Nondeterministic Alternating inflationary noninflationary Classical fixpoint logic: FP(D,i) Partial fixpoint logic: FP(D,n)
Relational complexity and fixpoint logics EXPTIME EXPTIME = FP(A,n) r PSPACE PSPACE = FP(D,n) = FP(N,n) = FP(A,i) r NP NP = FP(N,i) r P P = FP(D,i) r
Computational complexity and fixpoint logics EXPTIME FP(A,n) PSPACE FP(D,n) = FP(N,n) = FP(A,i) NP FP(N,i) P FP(D,i)
Computational complexity and fixpoint logics P = NP iff FP(D,i) = FP(N,i) P = PSPACE iff FP(D,i) = FP(D,n) NP = PSPACE iff FP(N,i) = FP(N,n) PSPACE = EXPTIME iff FP(A,i) = FP(A,n)
Computational complexity and fixpoint logics P = NP iff FP(D,i) = FP(N,i) P = PSPACE iff FP(D,i) = FP(D,n) NP = PSPACE iff FP(N,i) = FP(N,n) PSPACE = EXPTIME iff FP(A,i) = FP(A,n) [Abiteboul, V_]
