archives

Weakly Hard Problems


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Lutz, Jack H. (1993) Weakly Hard Problems. Technical Report TR93-13, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

Weakly Hard Problems
by
Jack H. Lutz
A weak completeness phenomenon is investigated in the complexity class
E= DTIME(2^linear).  According to standard terminology, a language H
is polynomial-time many-one hard for E if the set Pm(H), consisting of
all languages A that are polynomial-time many-one reducible to H,
contains the entire class E.  A language C is polynomial-time many-one
complete for E if it is polynomial-time many-one hard for E and is
also an element of E.  Generalizing this, a language H is weakly
polynomial-time many-one hard for E if the set Pm(H) does not have
measure 0 in E.  A language C is weakly polynomial-time many-one
complete for E if it is weakly polynomial-time many-one hard for E and
is also an element of E.
The main result of this paper is the construction of a language that
is weakly polynomial-time many-one complete, but not polynomial-time
many-one complete, for E. The existence of such languages implies that
previously known strong lower bounds on the complexity of weakly
polynomial-time many-one hard problems for E (given by work of Lutz,
Mayordomo, and Juedes) are indeed more general than the corresponding
bounds for polynomial-time many-one hard problems for E.
The proof of this result introduces a new diagonalization method,
called martingale diagonalization.  Using this method, one
simultaneously develops an infinite family of polynomial time
computable martingales (betting strategies) and a corresponding family
of languages that defeat these martingales (prevent them from winning
too much money) while also pursuing another agenda.  Martingale
diagonalization may be useful for a variety of applications.

Subjects:All uncategorized technical reports
ID code:00000049
Deposited by:Staff Account on 22 December 1993



Contact site administrator at: ssg@cs.iastate.edu