**Reading**PAGE

### Peer Evaluation activity

Trusted by | 1 |

Downloads | 3 |

Views | 25 |

### Total impact ?

#### Send a

### Eric has...

Trusted | 2 |

Reviewed | 0 |

Emailed | 0 |

Shared/re-used | 0 |

Discussed | 0 |

Invited | 0 |

Collected | 0 |

### This was brought to you by:

# Followblock this user
Eric Allender
*Trusted member*

## Professor

Dept. of Computer Science, Rutgers University, Piscataway, NJ

# Avoiding Simplicity is Complex

## Oh la la

Your session has expired but *don’t worry*, your message

has been saved.Please log in and we’ll bring you back

to this page. You’ll just need to click “Send”.

**Your evaluation**is of great value to our authors and readers. Many thanks for your time.

Your **mailing list** is currently empty.

It will build up as you send messages

and links to your peers.

__No one__besides you has access to this list.

Enter the e-mail addresses of your recipients in the box below.

__Note__: Peer Evaluation will NOT store these email addresses log inYour message has been sent.

### Description

New Full text for this article was not available? Send a request to the author(s).

**Title**: Avoiding Simplicity is Complex

**Author(s)**: Eric Allender, Holger Spakowski

**Abstract**: It is a trivial observation that every decidable set has strings of length n with Kolmogorov complexity logn+O(1) if it has any strings of length n at all. Things become much more interesting when one asks whether a similar property holds when one considers resource-bounded Kolmogorov complexity. This is the question considered here: Can a feasible set A avoid accepting strings of low resource-bounded Kolmogorov complexity, while still accepting some (or many) strings of lengthn? More specifically, this paper deals with two notions of resource-bounded Kolmogorov complexity: Kt and KNt. The measure Kt was defined by Levin more than three decades ago and has been studied extensively since then. The measure KNt is a nondeterministic analog of Kt. For all strings x, Kt(x)KNt(x); the two measures are polynomially related if and only if NEXPEXP/poly (Allender et al. in J.Comput. Syst. Sci. 77:1440, 2011). Many longstanding open questions in complexity theory boil down to the question of whether there are sets in P that avoid all strings of low Kt complexity. For example, the EXP vs ZPP question is equivalent to (one version of) the question of whether avoiding simple strings is difficult: (EXP=ZPP if and only if there exist >0 and a dense set in P having no strings x with Kt(x)x (Allender et al. in SIAM J. Comput. 35:14671493, 2006)). Surprisingly, we are able to show unconditionally that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NPcoNP contains infinitely many strings x such that KNt(x)x for every >0. The proof does not relativize. As an application, we are able to show that if E=NE, then accepting paths for nondeterministic exponential time machines can be found somewhat more quickly than the brute-force upper bound, if there are many accepting paths.

**Subject**: unspecified

**Area**: Other

**Language**: English

**Year**: 2011

Affiliations : |
Dept. of Computer Science, Rutgers University, Piscataway, NJ |

**Journal**: Theory of Computing Systems

**Issue**: x

**Publisher**: Springer New York

**Pages**: -

**Url**: http://www.springerlink.com/index/10.1007/s00224-011-9334-7

**Doi**: 10.1007/s00224-011-9334-7

### Leave a comment

### This contribution has not been reviewed yet. review?

You may receive the Trusted member label after :

• Reviewing **10 uploads**, whatever the media type.

• Being trusted by **10 peers**.

• If you are blocked by **10 peers** the "Trust label" will be suspended from your page. We encourage you to contact the administrator to contest the suspension.

#### Please select an affiliation to sign your evaluation:

#### Please select an affiliation:

### Eric's * Peer Evaluation activity*

Trusted by | 1 |

- FHeribert Vollmer,
*Professor*, Leibniz Universität Hannover.

Downloads | 3 |

Views | 25 |

- 1On strong separations from AC^0
- 1P-uniform circuit complexity
- 1On TC 0 , AC 0 , and Arithmetic Circuits
- 1Rudimentary reductions revisited 1 Introduction 2 Preliminaries
- 1A Note on the Representational Incompatibility of Function Approximation and Factored Dynam- ics
- 1A Note on the Representational Incompatabilty of Function Approximation and Factored Dynamics.
- 1On the complexity of numerical analysis
- 1Arithmetic Complexity, Kleene Closure, and Formal Power Series
- 1The complexity of computing maximal word functions
- 1Bounded depth arithmetic circuits: Counting and closure
- 1A First-Order Isomorphism Theorem
- 1Circuit Complexity before the Dawn of the New Millennium
- 1When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity
- 1Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds
- 1Randomness as Circuit Complexity ( and the Connection to Pseudorandomness )
- 1Cracks in the defenses: Scouting out approaches on circuit lower bounds
- 1Power from random strings
- 1The directed planar reachability problem
- 1A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics
- 1Uniform Derandomization from Pathetic Lower Bounds
- 1Circuit complexity before the dawn of the new millennium
- 1Arithmetic Circuits and Counting Complexity Classes
- 1Making computation count
- 1The complexity of satisfiability problems: Refining Schaefer's theorem☆
- 1Avoiding Simplicity is Complex

### Eric* has...*

Trusted | 2 |

- Moshe Vardi,
*Professor*. - Heribert Vollmer,
*Professor*.

Reviewed | 0 |

Emailed | 0 |

Shared/re-used | 0 |

Discussed | 0 |

Invited | 0 |

Collected | 0 |

## Full Text request

### Your request will be sent.

Please enter your email address to be notified

when this article becomes available

**Your email**