Luke Mathieson

3,611 reputation

1222

bio	website	comp.mq.edu.au/~lmathies
	location	Australia
	age	32
visits	member for	11 months
	seen	4 hours ago
stats	profile views	105

I'm a postdoc working on a big mess of different things, but all related by the use of parameterized complexity to help deal with hard problems. Mostly they're graph problems, but they come from all over the place. I'm also very interested in the structure of and relationships between complexity classes, especially in how they capture different, independent aspects of computation and its complexity.

	3,611 reputation	bio	website	comp.mq.edu.au/~lmathies	visits	member for	11 months
1222 badges		location	Australia		seen	4 hours ago

summary answers questions tags badges favorites bounties reputation activity

85 Answers

votes activity newest

11	If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?
10	If NP $\neq$ Co-NP then is P $\neq$ NP
9	Why isn't converting from an NFA to a DFA working?
9	Is a push-down automaton with two stacks equivalent to a turing machine?
9	Is SAT in P if there are exponentially many clauses in the number of variables?

3,611 Reputation

+55	Are there any problems in $APX - PTAS$ that are not $APX$-complete?
+10	How to find the pumping length of a context-free language?
+30	Graph Has Two / Three Different Minimal Spanning Trees?
+15	Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa

0 Questions

votes activity newest

This user has not asked any questions

67 Tags

83 complexity-theory × 27	36 graph-theory × 12
59 np-complete × 17	33 terminology × 7
55 reductions × 17	32 graphs × 11
49 automata × 11	31 computability × 7
38 formal-languages × 9	29 algorithms × 9

8 Accounts

	Computer Science	3,611 rep	1222
	Academia	1,196 rep	113
$Mathematics Stack Exchange$	Mathematics	807 rep	210
	Theoretical Computer Science	656 rep	215
	Stack Overflow	101 rep	2