Arrow Research search

Author name cluster

Martin Kummer

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.

7 papers
2 author rows

Possible papers

7

TCS Journal 1998 Journal Article

On the relative sizes of learnable sets

  • Lance Fortnow
  • Rūsiņs̆ Freivalds
  • William I. Gasarch
  • Martin Kummer
  • Stuart A. Kurtz
  • Carl H. Smith
  • Frank Stephan

Measure and category (or rather, their recursion-theoretical counterparts) have been used in theoretical computer science to make precise the intuitive notion “for most of the recursive sets”. We use the notions of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferable sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.

Details DOI

CSL Conference 1996 Conference Paper

Effective Strategies for Enumeration Games

  • Martin Kummer
  • Matthias Ott

Abstract We study the existence of effective winning strategies in certain infinite games, so called enumeration games. Originally, these were introduced by Lachlan (1970) in his study of the lattice of recursively enumerable sets. We argue that they provide a general and interesting framework for computable games and may also be well suited for modelling reactive systems. Our results are obtained by reductions of enumeration games to regular games. For the latter effective winning strategies exist by a classical result of Büchi and Landweber. This provides more perspicuous proofs for several of Lachlan's results as well as a key for new results. It also shows a way of how strategies for regular games can be scaled up such that they apply to much more general games.

Details

TCS Journal 1996 Journal Article

On resource-bounded instance complexity

  • Lance Fortnow
  • Martin Kummer

The instance complexity of a string x with respect to a set A and time bound t, ic t (x: A), is the length of the shortest program for A that runs in time t, decides x correctly, and makes no mistakes on other strings (where “do not know” answers are permitted). The instance complexity conjecture of Ko, Orponen, Schöning, and Watanabe (1986) states that for every recursive set A not in P and every polynomial t there is a polynomial t′ and a constant c such that for infinitely many x, ic t (x: A) ⩾ C t′ (x) − c, where C t′ (x) is the t′-time bounded Kolmogorov complexity of x. In this paper the conjecture is proved for all recursive tally sets and for all recursive sets which are NP-hard under honest reductions, in particular it holds for all natural NP-hard problems. The method of proof also yields the polynomialspace bounded and the exponential-time bounded versions of the conjecture in full generality. On the other hand, the conjecture itself turns out to be oracle dependent: In any relativized world where P = NP the conjecture holds, but there are also relativized worlds where it fails, even if C-complexity is replaced by Sipser's CD-complexity. Additionally it is proved that the instance complexity measure is noncomputable and it is investigated whether for every polynomial t there is a polynomial t′ such that C t′-complexity is bounded above by CDt -complexity.

Details DOI

MFCS Conference 1996 Conference Paper

On the Query Complexity of Sets

  • Richard Beigel
  • William I. Gasarch
  • Martin Kummer
  • Timothy H. McNicholl
  • Frank Stephan 0001

Abstract There has been much research over the last eleven years that considers the number of queries needed to compute a function as a measure of its complexity. We are interested in the complexity of certain sets in this context. We study the sets ODD A n ={(x 1, .. ., x n )∶¦ A ∩ { x 1, .. ., x n }¦ is odd} and WMOD( m ) A n ={( x 1, .. ., x n )∶¦ A ∩ { x 1, .. ., x n }¦≢0 (mod m )}. If A=K or A is semirecursive, we obtain tight bounds on the query complexity of ODD A n and WMOD( m ) A n. We obtain lower bounds for A r. e. The lower bounds for A r. e. are derived from the lower bounds for A semirecursive. We obtain that every tt-degree has a set A such that ODD A requires n n parallel queries to A, and a set B such that ODD B n can be decided with one query to B. Hence for bounded-query complexity, how information is packaged is more important than Turing degree. We investigate when extra queries add power. We show that, for several nonrecursive sets A, the more queries you can ask, the more sets you can decide; however, there are sets for which more queries do not help at all.

Details
v2026.09.13