Network profile

Hermann Gruber

Reputation

347

347
224
101

2017
2018
2019
2020

Top tag

complexity-theory

Next privilege

500 Rep.

Access review queues

Badges

2

9

Newest

Civic Duty

Next badge

0/1

Impact

5 posts edited

1 helpful flag

321 votes cast

Answers (10)

Votes Activity Newest

6	Are there any NP complete problems in SUB EXP TIME?
3	Graph problem known to be $NP$-complete only under Cook reduction
2	Origin of “Cookie” in Computing?
2	Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$
2	What are the axioms of automata theory?

View more →

Reputation (347)

+35	Origin of “Cookie” in Computing?
+2	Origin of “Cookie” in Computing?
+10	Is every linear language in NL?
+10	A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))

View more →

Questions (0)

Votes Activity Newest

This user has not asked any questions

Tags (17)

13 complexity-theory × 6	2 space-complexity × 2
4 np-complete × 2	2 terminology
3 graphs	2 history
3 reductions	2 algorithm-analysis
2 automata × 2	2 upper-bound

View more →

Bookmarks (19)

Votes Activity Newest Views Added

29	Longest Repeated (Scattered) Subsequence in a String
29	Graph problem known to be $NP$-complete only under Cook reduction
27	Is regex golf NP-Complete?
26	“Dense” regular expressions generate $\Sigma^*$?
24	Do undecidable languages exist in constructivist logic?

View more →

Accounts (5)

	Theoretical Computer Science	4,939 rep	1 gold badge26 silver badges51 bronze badges
	Computer Science	347 rep	2 silver badges9 bronze badges
	MathOverflow	193 rep	1 silver badge8 bronze badges
	History of Science and Mathematics	177 rep	6 bronze badges
	Area 51	151 rep	1 bronze badge

Badges (11)

Recent Class Name

Civic Duty	Yearling
Revival	Organizer
Citizen Patrol	Teacher
Excavator	Editor
Commentator	Supporter

View more →

Active bounties (0)

Active Offered Earned

This user has no active bounties

Votes cast (321)

all time			by type			month
321	up		155	question		5
0	down		166	answer		5

Computer Science Stack Exchange works best with JavaScript enabled