Network profile

Lwins

Reputation

360

360

Aug
Nov
Feb
May

Top tag

complexity-theory

Next privilege

500 Rep.

Access review queues

Badges

1

9

Newest

Critic

Next badge

4/5

Impact

0 posts edited

0 helpful flags

21 votes cast

Answers (4)

Votes Activity Newest

2	What is a good example of an NL-complete context free language?
1	Problem class of assigning N persons to N tasks, zero costs with prefs
1	Problems that provably require quadratic time
-1	Isn't NP problems always also co-NP problems?

Reputation (360)

This user has no recent positive reputation changes

View more →

Questions (4)

Votes Activity Newest

8	Can we convert an NFA to a regular expression of polynomial length?
7	Impossibility for Byzantine Generals Problem where $n \leq 3m$
3	Computational Irreducibility
2	Yao's minimax lemma for Monte Carlo algorithms

Tags (17)

3 complexity-theory × 4	1 resource-allocation
2 space-complexity	1 lower-bounds
2 context-free	1 assignment-problem
1 turing-machines × 2	1 complexity-classes
1 time-complexity	0 regular-expressions

View more →

Bookmarks (2)

Votes Activity Newest Views Added

12	What is complexity class $\oplus P^{\oplus P}$
8	How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?

Accounts (10)

	MathOverflow	1,277 rep	9 silver badges21 bronze badges
	Mathematics	594 rep	2 silver badges14 bronze badges
	Theoretical Computer Science	395 rep	1 silver badge13 bronze badges
	Computer Science	360 rep	1 silver badge9 bronze badges
	Physics	113 rep	4 bronze badges

Badges (10)

Recent Class Name

Critic	Tumbleweed
Commentator	Scholar
Yearling	Supporter
Revival	Editor
Teacher	Student

Active bounties (0)

Active Offered Earned

This user has no active bounties

Votes cast (21)

all time			by type
21	up		7	question
0	down		14	answer

Computer Science Stack Exchange works best with JavaScript enabled