Skip to main content
EXPTIME-complete's user avatar
EXPTIME-complete's user avatar
EXPTIME-complete's user avatar
EXPTIME-complete
  • Member for 8 years, 5 months
  • Last seen more than a month ago
  • Universidad Complutense de Madrid, Madrid, Spain
7 votes
4 answers
569 views

Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

4 votes
0 answers
150 views

(PCP theorem) Any natural decision problem defined in the format of PCP-verifiers?

3 votes
0 answers
144 views

Approximation class of finding decision trees with minimal depth

3 votes
1 answer
252 views

Which is the approximation class of Minimum 0-1 integer programming if only non-negative integers are allowed?

3 votes
1 answer
324 views

Looking for approximation class between NPO and Exp-APX

2 votes
1 answer
550 views

Is there any known Poly-APX-complete minimimization problem?

1 vote
0 answers
137 views

Does the NP-hardness of finding any valid solution imply NPO-hardness?

1 vote
0 answers
147 views

Looking for an implementation of any PCP-verifier for any NP problem

0 votes
0 answers
118 views

Complexity of, given any elementary function $f$ and a natural $n$, compute $n$ digits of $f(x)$