Richard Beigel, David Eppstein

We consider worst case time bounds for NP-complete problems

including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring.

Our algorithms are based on a common generalization of these problems,

called symbol-system satisfiability or, briefly, SSS [R. Floyd &

R. Beigel, The Language of Machines]. 3-SAT is equivalent to

(2,3)-SSS while the other problems ...
more >>>

Richard Beigel, William Gasarch, Efim Kinber

For a set A and a number n let F_n^A(x_1,...,x_n) =

A(x_1)\cdots A(x_n). We study how hard it is to approximate this

function in terms of the number of queries required. For a general

set A we have exact bounds that depend on functions from coding

theory. These are applied ...
more >>>

Anna Palbom

In an attempt to generalize Christofides algorithm for metric TSP to the asymmetric TSP with triangle inequality we have studied various properties of directed spanning cacti. In this paper we first observe that finding the TSP in a directed, weighted complete graph with triangle inequality is polynomial time equivalent to ... more >>>

Scott Aaronson

Can NP-complete problems be solved efficiently in the physical universe?

I survey proposals including soap bubbles, protein folding, quantum

computing, quantum advice, quantum adiabatic algorithms,

quantum-mechanical nonlinearities, hidden variables, relativistic time

dilation, analog computing, Malament-Hogarth spacetimes, quantum

gravity, closed timelike curves, and "anthropic computing." The ...
more >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Michael Blondin, Andreas Krebs, Pierre McKenzie

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem ... more >>>

Titus Dose, Christian Glaßer

The article investigates the relation between three well-known hypotheses.

1) Hunion: the union of disjoint complete sets for NP is complete for NP

2) Hopps: there exist optimal propositional proof systems

3) Hcpair: there exist complete disjoint NP-pairs

The following results are obtained:

a) The hypotheses are pairwise independent ...
more >>>