# Questions tagged [np-complete]

Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

659 questions
Filter by
Sorted by
Tagged with
255 views

### Distributing marbles into buckets for maximal colour sharing

i've got a problem that feels very much like it's NP-hard but I would love some help proving it primarily. Secondary to that, if an optimal polynomal time algorithm can be proposed that is even better,...
1 vote
29 views

### Why finding the shortest solution for a linear Diophantine equation is a NP problem?

I read this paper saying: ...finding the shortest solution for a linear Diophantine equation is a NP problem? I have two questions: 1). What it means of "the shortest solution" for linear ...
1 vote
30 views

### When we necessarily need monadic second order logic

I am a student of graph theory and recently started learning mathematical logic. If I am not wrong, any problem in the class Np-Complete can be represented as a SAT formula. As boolean formulas are a ...
21 views

408 views

### What does "NP-hard to distinguish ... between ... and ..." mean?

I am reading paper Hardness Results for Weaver’s Discrepancy Problem. In the abstract, the paper reads it is NP-hard to distinguish such a list of vectors for which there is a signed sum that equals ...
56 views

### Is convex program with exponential constraints NP-Hard

Convex optimization is widely known to be solvable in polynomial time, but is it still true when a convex program has an exponential number of constraints? For example, I have a convex program as ...
31 views

1 vote
23 views

### Special graphs with efficient minimum clique cover solutions

I would like to obtain a list of special graphs where there exist polynomial algorithms to find the minimum (vertex) clique cover. Some of the known cases are: Perfect graph including bipartite ...
1 vote