All Questions

12,298 questions
Filter by
Sorted by
Tagged with
645 views

Proof of a unique homomorphism from an initial object

What is the proof that there is only one homomorphism from an initial object to another object?
• 293
740 views

What evidence is there that $coRP \neq NP$?

What evidence is there that $coRP \neq NP$? $coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input ...
• 5,026
679 views

• 1,704
2k views

What are the consequences of Parity-L = P?

Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or ...
• 8,871
96k views

Major unsolved problems in theoretical computer science?

Wikipedia only lists two problems under "unsolved problems in computer science": P = NP? The existence of one-way functions What are other major problems that should be added to this list? Rules: ...
1k views

How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about ...
• 2,025
6k views

What would be the consequences of factoring being NP-complete?

Are there any references covering this?
• 793
913 views

Can it be determined if language L lies in NP?

Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
• 793
38k views

Is integer factorization an NP-complete problem? [duplicate]

Possible Duplicate: What are the consequences of factoring being NP-complete? What notable reference works have covered this?
• 793
346 views

Finding odd holes in circulant Paley graphs

The Paley graphs Pq are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a2 ...
• 8,871
385 views

Computational query complexity of SQ-learning

It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic ...
• 9,820
3k views

The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the ...
• 962
4k views

Applications of TCS to classical mathematics?

We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.). What are some examples of when it has gone the other way around? Here ...