Questions tagged [average-case-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
37 votes
2 answers
6k views

Status of Impagliazzo's Worlds?

In 1995, Russell Impagliazzo proposed five complexity worlds: 1- Algorithmica: $P=NP$ with all the amazing consequences. 2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) ...
Mohammad Al-Turkistany's user avatar
20 votes
1 answer
731 views

Problems in NP but not in Average-P/poly

The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\...
Sadeq Dousti's user avatar
  • 16.5k
16 votes
2 answers
514 views

Paradigms for complexity analysis of algorithms

Worst-case and average case analysis are well-known measures for the complexity of an algorithm. Recently smoothed analysis has emerged as another paradigm to explain why some algorithms which are ...
Opt's user avatar
  • 1,311
14 votes
4 answers
1k views

Are there any known NP problems which are conjectured to be exponentially hard on average?

ETH states that SAT cannot be solved in the worst case in subexponential time. What about average case? Are there natural problems in NP that are conjectured to be exponentially hard in the average ...
Anonymous's user avatar
  • 4,041
11 votes
2 answers
2k views

Worst case to average case reductions

Are there problems whose average case complexity is the same as their worst case complexity? What are the underlying properties of these problems that makes reducing the worst case to the average case ...
Anonymous's user avatar
  • 4,041
10 votes
1 answer
378 views

Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. Assuming the problem of FACTORING:[Given $N ...
Omid Etesami's user avatar
5 votes
0 answers
242 views

Non-uniform average-case complexity of NP

It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...
Vanessa's user avatar
  • 2,151
5 votes
1 answer
328 views

Average-case complexity open problems other than one-way functions

The list of unsolved problems in computer science on Wikipedia lists no problems in average-case complexity, except "Do one-way functions exist?" which is whether there is a polynomial time computable ...
Saram Meti's user avatar
-2 votes
1 answer
412 views

Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof? Are there other non-trivial examples of random self-reducibility? Is there a good reference?
Turbo's user avatar
  • 12.9k