Stack Exchange Network

Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Loading…
  1. 0
  2. +0
    • Tour Start here for a quick overview of the site
    • Help Center Detailed answers to any questions you might have
    • Meta Discuss the workings and policies of this site
    • About Us Learn more about Stack Overflow the company
    • Business Learn more about hiring developers or posting ads with us
  3. Log in Sign up
  4. current community

    • Theoretical Computer Science
      help chat
    • Theoretical Computer Science Meta

    your communities

    Sign up or log in to customize your list.

    more stack exchange communities

    company blog
Theoretical Computer Science
  1. Home
    1. Questions
    2. Tags
    3. Users
    4. Unanswered
    5. Jobs
Profile Activity
Meta user
Network profile
Andras Farago

Reputation

10,372
  • 10.4k
  • 9.7k
  • 8.9k
  • 2018
  • 2019
  • 2020
  • 2021

Top tag

cc.complexity-theory

Next privilege

15,000 Rep.
Protect questions

Badges

29
66

Newest

 Yearling

Next badge

0/1
Excavator

Impact

~63k
people reached
0 posts edited
0 helpful flags
364 votes cast
Summary Answers Questions Tags Badges Bookmarks Bounties Reputation All actions

61 Questions

Votes Activity Newest Views
15
54
votes
7
answers
4k
views

For which problems in P is it easier to verify the result than to find it?

cc.complexity-theory ds.algorithms reference-request
Nov 20 '15 at 18:08 Yonatan N 1,550
13
45
votes
8
answers
5k
views

Obituaries of dead conjectures

cc.complexity-theory ds.algorithms
Oct 7 '15 at 16:04 Community♦ 1
9
38
votes
4
answers
1k
views

Examples where the uniqueness of the solution makes it easier to find

cc.complexity-theory ds.algorithms graph-algorithms complexity-classes unique-solution
Jun 20 '18 at 16:38 Mohammad Al-Turkistany 20.1k
5
36
votes
4
answers
3k
views

Hardness of approximation without the PCP theorem

cc.complexity-theory approximation-hardness pcp
Mar 14 '14 at 3:16 Artem Kaznatcheev♦ 9,993
7
36
votes
3
answers
916
views

Why does randomness have stronger effect on reductions than on algorithms?

cc.complexity-theory reductions derandomization
Jan 14 '14 at 10:12 Niel de Beaudrap 8,709
8
34
votes
3
answers
1k
views

Hardest known natural problem in P?

cc.complexity-theory ds.algorithms
Oct 2 '14 at 23:18 D.W. 9,606
9
33
votes
5
answers
4k
views

The unreasonable power of non-uniformity

cc.complexity-theory complexity-classes big-picture
May 2 '14 at 12:07 Thomas Klimpel 2,963
13
31
votes
6
answers
2k
views

Why are so few natural candidates for NP-intermediate status?

cc.complexity-theory p-vs-np np-intermediate
Mar 14 '14 at 10:09 Community♦ 1
16
29
votes
16
answers
5k
views

Hard-looking algorithmic problems made easy by theorems

cc.complexity-theory ds.algorithms graph-algorithms
Nov 12 '15 at 9:20 Emil JeÅ™ábek 12.8k
5
25
votes
2
answers
1k
views

Is there an NP-complete language that contains precisely half of the n-bit instances?

cc.complexity-theory np np-complete
Nov 29 '16 at 4:42 Kaveh 21k
2
23
votes
2
answers
602
views

Which graph parameters are NOT concentrated on random graphs?

graph-theory pr.probability random-graphs
Jun 3 '19 at 8:02 Yuval Peres 336
3
23
votes
3
answers
1k
views

How much would a SAT oracle help speeding up polynomial time algorithms?

cc.complexity-theory np np-complete
Sep 29 '15 at 23:21 Joshua Grochow 34.1k
2
23
votes
10
answers
2k
views

Problems that are easy on unweighted graphs, but hard for weighted graphs

cc.complexity-theory graph-algorithms np-hardness
Jan 26 '15 at 14:09 Community♦ 1
3
23
votes
3
answers
982
views

Optimization problems with good characterization, but no polynomial-time algorithm

cc.complexity-theory graph-algorithms complexity-classes optimization linear-programming
Feb 16 '14 at 9:38 Rahul Savani 1,683
4
21
votes
1
answer
598
views

Is P equal to the intersection of all superpolynomial time classes?

cc.complexity-theory ds.algorithms complexity-classes
Sep 21 '14 at 23:05 Huck Bennett 4,412
8
20
votes
1
answer
758
views

“Almost easy” NP-complete problems

cc.complexity-theory ds.algorithms complexity-classes np-complete
Nov 18 '15 at 3:17 Andras Farago 10.4k
2
20
votes
1
answer
860
views

Time complexity with irrational exponent?

cc.complexity-theory time-complexity polynomial-time
Sep 27 '15 at 0:27 Joe Bebel 2,265
4
19
votes
2
answers
564
views

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

cc.complexity-theory circuit-complexity ho.history-overview
May 12 '14 at 1:54 Community♦ 1
3
18
votes
1
answer
491
views

Natural candidate against the Isomorphism Conjecture?

cc.complexity-theory complexity-classes p-vs-np np-complete
Feb 28 '14 at 13:06 Artem Kaznatcheev♦ 9,993
6
17
votes
3
answers
1k
views

How common is phase transition in NP-complete problems?

cc.complexity-theory phase-transition
Feb 11 '17 at 0:41 daniel pehoushek 115
5
16
votes
1
answer
441
views

What is the complexity of this graph problem?

graph-theory graph-algorithms np-hardness
Feb 21 '18 at 14:44 Marzio De Biasi 21.7k
2
16
votes
3
answers
470
views

Complexity class separations without hierarchy theorems

cc.complexity-theory complexity-classes hierarchy-theorems
Feb 28 '14 at 21:27 Community♦ 1
2
13
votes
3
answers
2k
views

What would be the consequences of PH=PSPACE?

cc.complexity-theory complexity-classes conditional-results
Feb 23 '14 at 21:51 Community♦ 1
1
12
votes
3
answers
737
views

Nontrivial problems solvable in constant time?

cc.complexity-theory ds.algorithms time-complexity
Oct 13 '15 at 22:50 David Eppstein 49.3k
 
12
votes
1
answer
273
views

Slowest many-one reduction?

cc.complexity-theory reductions np-complete
Oct 3 '15 at 12:07 Community♦ 1
2
12
votes
2
answers
682
views

What is the complexity of this path problem?

cc.complexity-theory graph-theory graph-algorithms
Mar 10 '14 at 3:39 Community♦ 1
1
12
votes
3
answers
408
views

NP-complete graph property that is hereditary, but not additive?

cc.complexity-theory graph-theory graph-algorithms np
Mar 2 '14 at 12:50 Super8 304
3
11
votes
1
answer
195
views

Natural candidates for NP-E and E-NP

cc.complexity-theory complexity-classes np-complete
Jan 26 '19 at 12:19 Lance Fortnow 8,351
1
11
votes
4
answers
859
views

Does NP-completeness/hardness have to be constructive?

cc.complexity-theory np-hardness reductions
Aug 29 '15 at 8:15 Mohammad Al-Turkistany 20.1k
2
11
votes
1
answer
259
views

Randomized Polynomial Hierarchy?

cc.complexity-theory randomized-algorithms randomness
Aug 28 '15 at 12:05 Emil JeÅ™ábek 12.8k
1
2 3 Next
Theoretical Computer Science
  • Tour
  • Help
  • Chat
  • Contact
  • Feedback
  • Mobile
Company
  • Stack Overflow
  • For Teams
  • Advertise With Us
  • Hire a Developer
  • Developer Jobs
  • About
  • Press
  • Legal
  • Privacy Policy
  • Terms of Service
Stack Exchange
Network
  • Technology
  • Life / Arts
  • Culture / Recreation
  • Science
  • Other
  • Stack Overflow
  • Server Fault
  • Super User
  • Web Applications
  • Ask Ubuntu
  • Webmasters
  • Game Development
  • TeX - LaTeX
  • Software Engineering
  • Unix & Linux
  • Ask Different (Apple)
  • WordPress Development
  • Geographic Information Systems
  • Electrical Engineering
  • Android Enthusiasts
  • Information Security
  • Database Administrators
  • Drupal Answers
  • SharePoint
  • User Experience
  • Mathematica
  • Salesforce
  • ExpressionEngine® Answers
  • Stack Overflow em Português
  • Blender
  • Network Engineering
  • Cryptography
  • Code Review
  • Magento
  • Software Recommendations
  • Signal Processing
  • Emacs
  • Raspberry Pi
  • Stack Overflow на русском
  • Code Golf
  • Stack Overflow en español
  • Ethereum
  • Data Science
  • Arduino
  • Bitcoin
  • Software Quality Assurance & Testing
  • Sound Design
  • Windows Phone
  • more (28)
  • Photography
  • Science Fiction & Fantasy
  • Graphic Design
  • Movies & TV
  • Music: Practice & Theory
  • Worldbuilding
  • Video Production
  • Seasoned Advice (cooking)
  • Home Improvement
  • Personal Finance & Money
  • Academia
  • Law
  • Physical Fitness
  • Gardening & Landscaping
  • Parenting
  • more (10)
  • English Language & Usage
  • Skeptics
  • Mi Yodeya (Judaism)
  • Travel
  • Christianity
  • English Language Learners
  • Japanese Language
  • Chinese Language
  • French Language
  • German Language
  • Biblical Hermeneutics
  • History
  • Spanish Language
  • Islam
  • Русский язык
  • Russian Language
  • Arqade (gaming)
  • Bicycles
  • Role-playing Games
  • Anime & Manga
  • Puzzling
  • Motor Vehicle Maintenance & Repair
  • Board & Card Games
  • Bricks
  • Homebrewing
  • Martial Arts
  • The Great Outdoors
  • Poker
  • Chess
  • Sports
  • more (16)
  • MathOverflow
  • Mathematics
  • Cross Validated (stats)
  • Theoretical Computer Science
  • Physics
  • Chemistry
  • Biology
  • Computer Science
  • Philosophy
  • Linguistics
  • Psychology & Neuroscience
  • Computational Science
  • more (10)
  • Meta Stack Exchange
  • Stack Apps
  • API
  • Data
  • Blog
  • Facebook
  • Twitter
  • LinkedIn
  • Instagram

site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2021.3.5.38726