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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>