Search
Now showing items 1-10 of 13
Using Self-Reducibilities to Characterize Polynomial Time
(University of Wisconsin-Madison Department of Computer Sciences, 1988)
A Survey of Some Recent Results on Computation Complexity in Weak Theories of Arithmetic
(University of Wisconsin-Madison Department of Computer Sciences, 1984)
Self-Reducibility: The Effects of Structure on Complexity
(University of Wisconsin-Madison Department of Computer Sciences, 1988)
Near-Testable Sets
(University of Wisconsin-Madison Department of Computer Sciences, 1988)
On the Complexity of Reachability and Motion Planning Questions
(University of Wisconsin-Madison Department of Computer Sciences, 1985)
Kolmogorov Complexity, Restricted Nondeterminism and Generalized Spectra
(University of Wisconsin-Madison Department of Computer Sciences, 1989)
This paper uses the technique of generalized spectra and expressibility of complexity classes in logic, developed by Fagin and Immerman, to give alternate characterizations of specific subclasses of NP. These characterizations ...
Self-Reducible, P-selective, Near-testable, and P-cheatable Sets: The Effect of Internal Structure on the Complexity of a Set
(University of Wisconsin-Madison Department of Computer Sciences, 1988)
A Structural Overview of NP Optimization Problems
(University of Wisconsin-Madison Department of Computer Sciences, 1989)
Efficient Algorithms for Polyhedron Collision Detection
(University of Wisconsin-Madison Department of Computer Sciences, 1987)
A Note on Bi-Immunity and P-Closeness of P-Cheatable Sets in P/poly
(University of Wisconsin-Madison Department of Computer Sciences, 1988)