Author name cluster

Stephen Travers

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

I&C Journal 2011 Journal Article

The fault tolerance of NP-hard problems

Christian Glaßer
A. Pavan
Stephen Travers

We study the effects of faulty data on NP-hard sets. We consider hard sets for several polynomial time reductions, add corrupt data and then analyze whether the resulting sets are still hard for NP. We explain that our results are related to a weakened deterministic variant of the notion of program self-correction by Blum, Luby, and Rubinfeld. Among other results, we use the Left-Set technique to prove that m-complete sets for NP are nonadaptively weakly deterministically self-correctable while btt-complete sets for NP are weakly deterministically self-correctable. Our results can also be applied to the study of Yesha’s p-closeness. In particular, we strengthen a result by Ogiwara and Fu.

Details DOI

TCS Journal 2009 Journal Article

Non-mitotic sets

Christian Glaßer
Alan L. Selman
Stephen Travers
Liyu Zhang

We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that • 1-tt-mitoticity and m-mitoticity differ on NP. • T-autoreducibility and T-mitoticity differ on NP (this contrasts the situation in the recursion theoretic setting, where Ladner showed that autoreducibility and mitoticity coincide). • 2-tt-autoreducibility does not imply weak 2-tt-mitoticity (from this it follows that autoreducibility and mitoticity are not equivalent for all reducibilities between 2-tt and T, although the notions coincide for m- and 1-tt-reducibility).

Details DOI

TCS Journal 2006 Journal Article

The complexity of membership problems for circuits over sets of integers

Stephen Travers

We investigate the complexity of membership problems for { ∪, ∩, -, +, × } -circuits computing sets of integers. These problems are a natural modification of the membership problems for circuits computing sets of natural numbers studied by McKenzie and Wagner [The complexity of membership problems for circuits over sets of natural numbers, Lecture Notes in Computer Science, Vol. 2607, 2003, pp. 571–582]. We show that there are several membership problems for which the complexity in the case of integers differs significantly from the case of the natural numbers: testing membership in the subset of integers produced at the output of a { ∪, +, × } -circuit is NEXPTIME-complete, whereas it is PSPACE-complete for the natural numbers. As another result, evaluating { -, + } -circuits is shown to be P-complete for the integers and PSPACE-complete for the natural numbers. The latter result extends McKenzie and Wagner's work in nontrivial ways. Furthermore, evaluating { × } -circuits is shown to be NL ∧ ⊕ L -complete, and several other cases are resolved.

Details DOI