Luke Mathieson

3,546 reputation

220

bio	website	comp.mq.edu.au/~lmathies
	location	Australia
	age	32
visits	member for	11 months
	seen	7 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,546 reputation	bio	website	comp.mq.edu.au/~lmathies	visits	member for	11 months
220 badges		location	Australia		seen	7 hours ago

summary answers questions tags badges favorites bounties reputation activity

84 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,546 Reputation

+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
+20	Wheel subgraph problem
+10	Reduction from Vertex Cover to an Independent Set problem

0 Questions

votes activity newest

This user has not asked any questions

67 Tags

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

8 Accounts

	Computer Science	3,546 rep	220
	Academia	1,196 rep	113
$Mathematics Stack Exchange$	Mathematics	807 rep	110
	Theoretical Computer Science	656 rep	215
	Stack Overflow	101 rep	2