Linked Questions

30
votes
6answers
2k views

Is there a natural problem on the naturals that is NP-complete?

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
20
votes
3answers
1k views

Problems that are NP-complete under randomized or P/poly reductions.

In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which ...
12
votes
2answers
1k views

List of number theoretic or algebraic problems in various complexity classes

I am looking for a list about the known or unknown complexity of various number theoretic /algebraic problems. For example, GCD in $NC^1$ is open, factoring in $P$ is open, computing sheaf ...
15
votes
3answers
3k views

Subset sum vs. Subset product (strong vs. weak NP hardness)

I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard. Subset Sum: Given $X = \{x_1,...,...
3
votes
1answer
966 views

What NP-complete problems are most similar to integer factoring?

The exact complexity of factoring integers (the decision problem) is a major open question in TCS (with important implications, especially in cryptography because of the RSA algorithm), and is widely ...
4
votes
2answers
496 views

NP-complete variants of NPI problems

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
2
votes
2answers
576 views

Strongly NP-complete variants of subset sum or partition problem

Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA ...
-3
votes
1answer
319 views

Consequences of polynomial time algorithm to variant of integer factorization

Given $N,U,V\in\Bbb N$ is there $n\in[U,V]\cap\Bbb N$ such that $n|N$ is $\mathsf{NP}$-complete modulo Cramer's conjecture on prime gaps is shown in An NP-complete variant of factoring. So supposing ...
2
votes
0answers
111 views

An NP-complete variant of factoring and relation to factoring [closed]

After reading this post An NP-complete variant of factoring. I come up with a question. To summerize the post, we have the factoring problem (F) which ask for a number $p$ that is prime and divides ...
0
votes
0answers
66 views

Complexity of variant polynomial factorization

Few years back a question on whether a variant of integer factorization was $\mathsf{NP}$ complete was asked, which according to state of mathematics today does not have a conclusive answer. Is ...