Kaveh

Member for 11 years, 7 months
Last seen this week

cs.toronto.edu/~kaveh
Toronto, Canada

Summary

Reputation

22,103

22.1k
20.8k
19.5k

2020
2021
2022
2023

Top tag

complexity-theory

Next privilege

25,000 Rep.

Access to site analytics

Badges

4

50

110

Newest

Nice Answer

Next badge

84/100

Sportsmanship

Answers

View all 151 answers

Score Activity Newest

458

What is the definition of P, NP, NP-complete and NP-hard?

Feb 7, 2013

229

What is the definition of P, NP, NP-complete and NP-hard?

Dec 5, 2013

73

Are there subexponential-time algorithms for NP-complete problems?

Feb 15, 2013

60

How not to solve P=NP?

May 17, 2012

47

Knapsack problem -- NP-complete despite dynamic programming solution?

Mar 31, 2012

Questions

View all 18 questions

Score Activity Newest Views

40

Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

Sep 13, 2012

32

Rice's theorem for non-semantic properties

Mar 6, 2012

21

Easy reduction from 3SAT to Hamiltonian path problem

Mar 11, 2012

21

How to formulate a computational problem rigorously?

Jul 8, 2013

20

Extension of SQL capturing $\mathsf{P}$

Mar 8, 2012

Tags

View all 123 tags

complexity-theory

1,325

Score

86

posts

p-vs-np

828

Score

11

posts

terminology

788

Score

16

posts

reference-question

785

Score

5

posts

complexity-classes

756

Score

16

posts

Reputation

+10

What is the definition of P, NP, NP-complete and NP-hard?

+10

Why does a polynomial-time language have a polynomial-sized circuit?

+10

What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?

+10

Why is writing down mathematical proofs more fault-proof than writing computer code?

Badges

View all badges

4

gold badges

Great Answer

× 2

Sep 10, 2016
Electorate

Sep 4, 2014
Famous Question

Feb 14, 2022

50

silver badges

Convention

Mar 21, 2012
Generalist

Apr 6, 2016
Beta

Mar 20, 2012

110

bronze badges

computability

Jan 22, 2013
complexity-theory

Jul 24, 2012
Tag Editor

Mar 30, 2012

Accounts

View all 17 accounts

Computer Science

22.1k
4
50
110

Theoretical Computer Science

21.4k
8
82
182

5,224
2
35
51

3,718
24
39

3,492
27
37

Active bounties (0)

Active Offered Earned

This user has no active bounties

Votes cast

2,170

upvotes

110

downvotes

689

question votes

1,591

answer votes