Jan Johannsen

less info

network profile

1,392 reputation

516

bio	website	www2.tcs.ifi.lmu.de/~jjohanns
	location	Munich, Germany
	age	47
visits	member for	1 year, 9 months
	seen	6 hours ago
stats	profile views	130

TCS researcher at LMU Munich. I am interested in computational complexity and logic, especially where the two intersect. My main field of work is propositional proof complexity.

summary answers questions tags badges favorites bounties reputation activity

18 Answers

votes activity newest

16	$\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}\|\|}$
15	Golden ratio or Pi in the running time
14	minimum true monotone 3SAT
10	Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?
8	Set of functions computable in polynomial time

view more

1,392 Reputation

+20	Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$
+20	Simply-stated restriction on imperative programming language that captures the elementary functions?
+50	A 3-CNF formula that requires resolution width $5$
+10	Golden ratio or Pi in the running time

view more

2 Questions

votes activity newest

18	Uses of XORification
10	A 3-CNF formula that requires resolution width $5$

25 Tags

83 cc.complexity-theory × 13	15 big-list × 3
32 reference-request × 8	14 np-hardness
30 complexity-classes × 4	12 computability × 2
18 lo.logic × 6	10 structural-complexity
17 sat × 5	9 circuit-complexity × 2

view more

1 Account

Theoretical Computer Science

1,392 rep

516

15 Badges

recent class name

Necromancer × 3	Yearling
Nice Question × 2	Scholar
Informed	Commentator
Enlightened	Student
Nice Answer × 4	Critic

view more

0 Active bounties

active offered earned

This user has no active bounties

231 Votes Cast

all time			by type			month
223	up		96	question		6
8	down		135	answer		6

Technology			Life / Arts	Culture / Recreation	Science	Other
Stack Overflow Server Fault Super User Web Applications Ask Ubuntu Webmasters Game Development TeX - LaTeX	Programmers Unix & Linux Ask Different (Apple) WordPress Answers Geographic Information Systems Electrical Engineering Android Enthusiasts IT Security	Database Administrators Drupal Answers SharePoint User Experience Mathematica more (14)	Photography Science Fiction & Fantasy Seasoned Advice (cooking) Home Improvement more (13)	English Language & Usage Skeptics Mi Yodeya (Judaism) Travel Christianity Arqade (gaming) Bicycles Role-playing Games more (21)	Mathematics Cross Validated (stats) Theoretical Computer Science Physics more (7)	Stack Apps Meta Stack Overflow Area 51 Stack Overflow Careers

site design / logo © 2013 stack exchange inc; user contributions licensed under cc-wiki with attribution required

rev 2013.6.19.752

Theoretical Computer Science Stack Exchange works best with JavaScript enabled