Network profile

user5721565

Reputation

209

209

Jun
Sep
Dec
Mar

Top tag

context-free

Next privilege

250 Rep.

View close votes

Badges

2

7

Newest

Commentator

Next badge

0/1

Impact

1 post edited

0 helpful flags

71 votes cast

10 Bookmarks

Votes Activity Newest Views Added

288

votes

7

answers

135k

views

What is the definition of P, NP, NP-complete and NP-hard?

complexity-theory terminology complexity-classes p-vs-np reference-question

Apr 19 at 23:23 Community♦ 1

20

votes

2

answers

19k

views

Is the complement of { ww | … } context-free?

formal-languages context-free formal-grammars

Nov 21 '18 at 15:27 Zhao Shun 1

9

votes

2

answers

376

views

Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

algorithms algorithm-analysis np-complete approximation max-cut

Dec 21 '19 at 15:40 John L. 24.8k

6

votes

2

answers

339

views

Prove that context free languages aren't closed under DropMiddle

formal-languages context-free closure-properties

Sep 12 '17 at 15:18 Community♦ 1

5

votes

1

answer

5k

views

Showing that Bayes classifier is optimal

machine-learning classification statistics

Mar 31 '17 at 11:22 Yuval Filmus 246k

4

votes

3

answers

4k

views

Show that P is closed against the Kleene star

complexity-theory closure-properties polynomial-time

Nov 16 '19 at 0:02 David Ferris 177

3

votes

1

answer

29

views

If P is a property of turing machines, does P $\leq_T$ COUNT_P imply that P $\in$ RE $\cup$ coRE?

turing-machines

Apr 6 '17 at 22:28 Yuval Filmus 246k

3

votes

1

answer

6k

views

Reduction of 3-SAT to Vertex Cover?

complexity-theory np-complete reductions satisfiability 3-sat

May 30 at 4:35 C Lu 21

3

votes

3

answers

884

views

Equivalence between alternative definitions of NP

complexity-theory computability turing-machines np nondeterminism

Apr 28 '17 at 21:18 gnasher729 21.6k

2

votes

0

answers

109

views

PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

np-complete approximation linear-programming knapsack-problems

Feb 21 '20 at 7:16 Tav 113

Computer Science Stack Exchange works best with JavaScript enabled