1. Home
2. Questions
3. Tags
5. Users
6. Jobs
7. Companies
8. Unanswered
Teams

Ask questions, find answers and collaborate at work with Stack Overflow for Teams.
Try Teams for free Explore Teams
Teams
Ask questions, find answers and collaborate at work with Stack Overflow for Teams. Explore Teams

Michael Wehar

Member for 11 years, 9 months
Last seen more than a month ago

GitHub
michaelwehar.com
Pennsylvania, USA

Summary

Reputation

5,167

5.2k
4.8k
4.5k

2021
2022
2023
2024

Top tag

cc.complexity-theory

Next privilege

10,000 Rep.

Access moderator tools

Badges

1

24

54

Newest

Yearling

Next badge

49/100

Sportsmanship

Impact

~62k

people reached

0

helpful flags

2,502

votes cast

Questions

View all 33 questions

25

Finding the smallest DFA that separates two words without using brute force search?

Jan 12, 2015

20

Is there a non-deterministic linear time algorithm for CNF-SAT?

Oct 22, 2015

18

What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

Apr 9, 2017

18

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

Sep 18, 2020

15

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

Nov 6, 2015

Answers

View all 28 answers

26

Deciding emptiness of intersection of regular languages in subquadratic time

Jan 17, 2015

24

Are there any open problems left about DFAs?

May 15, 2014

15

How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?

Mar 13, 2015

11

A simple decision problem whose decidability is not known

Oct 4, 2015

9

Career in Theoretical Computer Science

Oct 24, 2013

Tags

View all 72 tags

cc.complexity-theory

78

Score

39

posts

automata-theory

54

Score

12

posts

nondeterminism

39

Score

5

posts

regular-language

38

Score

3

posts

ds.algorithms

34

Score

7

posts

Reputation

+10

Are there more polynomial time problems with complexity lower bounds?

+10

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

+10

Is there a non-deterministic linear time algorithm for CNF-SAT?

+10

What is the complexity of counting parse trees?

Badges

View all badges

1

gold badge

Electorate

Jan 21, 2018

24

silver badges

Inquisitive

Sep 19, 2020
Taxonomist

Jun 17, 2018
Civic Duty

Aug 2, 2015

54

bronze badges

Altruist

Dec 8, 2014
Talkative

Oct 13, 2015
Investor

Nov 30, 2014

Accounts

View all 19 accounts

Theoretical Computer Science

5,167
1
24
54

393
3
13

Computer Science

246
2
12

221
1
8

191
13

Active bounties (0)

This user has no active bounties

Votes cast

2,501

upvotes

1

downvotes

1,344

question votes

1,158

answer votes