All reports by Author Joerg Flum:

__
TR13-065
| 21st April 2013
__

Yijia Chen, Joerg Flum#### On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity

__
TR12-018
| 24th February 2012
__

Joerg Flum, Moritz Müller#### Some definitorial suggestions for parameterized proof complexity

__
TR11-085
| 14th May 2011
__

Yijia Chen, Joerg Flum, Moritz Müller#### Hard instances of algorithms and proof systems

__
TR11-020
| 20th December 2010
__

Yijia Chen, Joerg Flum#### Listings and logics

__
TR10-008
| 13th January 2010
__

Yijia Chen, Joerg Flum#### On optimal proof systems and logics for PTIME

Revisions: 1

Yijia Chen, Joerg Flum

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P $\ne$ NP or NP $\ne$ coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>>

Joerg Flum, Moritz Müller

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

more >>>Yijia Chen, Joerg Flum, Moritz Müller

Assuming that the class TAUT of tautologies of propositional logic has no almost optimal algorithm, we show that every algorithm $\mathbb A$ deciding TAUT has a polynomial time computable sequence witnessing that $\mathbb A$ is not almost optimal. The result extends to every $\Pi_t^p$-complete problem with $t\ge 1$; however, we ... more >>>

Yijia Chen, Joerg Flum

There are standard logics DTC, TC, and LFP capturing the complexity classes L, NL, and P on ordered structures, respectively. In [Chen and Flum, 2010] we have shown that ${\rm LFP}_{\rm inv}$, the ``order-invariant least fixed-point logic LFP,'' captures P (on all finite structures) if and only if there is ... more >>>

Yijia Chen, Joerg Flum

We prove that TAUT has a $p$-optimal proof system if and only if $L_\le$, a logic introduced in [Gurevich, 88], is a P-bounded logic for P. Furthermore, using the method developed in [Chen and Flum, 10], we show that TAUT has no \emph{effective} $p$-optimal proof system under some reasonable complexity-theoretic ... more >>>