Network profile

Joni

Reputation

511

511
506
501

2017
2018
2019
2020

Top tag

complexity-theory

Next privilege

1,000 Rep.

See votes

Badges

3

11

Newest

Yearling

Next badge

0/1

Impact

0 posts edited

0 helpful flags

8 votes cast

8 Questions

Votes Activity Newest Views

3

10

votes

3

answers

690

views

Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$

time-complexity complexity-classes p-vs-np

Dec 13 '12 at 2:35 Juho 19.9k

1

9

votes

2

answers

211

views

Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$

complexity-theory satisfiability approximation

Dec 23 '12 at 9:24 Kaveh 20.4k

3

6

votes

1

answer

8k

views

Formalization of the shortest path algorithm to a linear program

algorithms graphs shortest-path linear-programming

Dec 23 '12 at 12:30 Marc Khoury 1,345

2

5

votes

1

answer

534

views

Showing that Independent set of size $k$ can be decided using logarithmic space

complexity-theory graphs space-complexity

Nov 27 '12 at 18:19 Juho 19.9k

5

votes

1

answer

353

views

Is the set of minimal DFA decidable?

formal-languages computability automata finite-automata

Aug 5 '12 at 14:43 Raphael♦ 67.6k

2

votes

2

answers

174

views

Assuming $\mbox{BPP}\subseteq \Pi_2$ -What conclusions can we make?

complexity-theory time-complexity

Dec 5 '17 at 16:36 Pawan Kumar 293

2

votes

1

answer

734

views

Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

turing-machines reductions undecidability halting-problem

Aug 2 '12 at 5:53 A.Schulz 11.6k

1

vote

2

answers

335

views

How come finding an $n/2$ size clique in a directed/ non directed graph is not in $\sf NL$?

complexity-theory time-complexity

Jan 30 '13 at 3:19 Kaveh 20.4k

Computer Science Stack Exchange works best with JavaScript enabled