Skip to main content

Questions tagged [np-complete]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
27 views

Deterministic algorithm in (non polynomial time) for computing tensor rank decomposition.

Thanks to the insights from this question, I have determined that I would like to find an algorithm for computing the tensor rank decomposition (or even just finding the tensor rank) of a tensor. In ...
Jack's user avatar
  • 424
0 votes
0 answers
22 views

How to understand 'the problem of determining the exact number of monomials in P(x) given by a black box is #P-Complete'

In this paper:https://dl.acm.org/doi/pdf/10.1145/62212.62241, what's given is $P(x)$ a (sparse) multivariate polynomial with real(or complex) coefficients. The author claimed two things. It is known ...
Youzhe Heng's user avatar
2 votes
0 answers
48 views

Dividing $N$ coins into at most $K$ groups such that I can get any number of coins by selecting whole groups

Problem Inspired from Dividing $100$ coins into $7$ groups such that I can choose any number of coins by selecting whole groups . I am interested in the number of possible ways we can get such a split....
EnEm's user avatar
  • 1,181
0 votes
0 answers
26 views

Quadratic Programming and Betweenness Problem

Given Betweenness problem of $n$ variables $x_1,...,x_n$ and $m$ triplets $(x_i,x_j,x_k)$, I build a Quadratic Programming for the triplets such that for every triplet $(x_i,x_j,x_k)$ I add $(2x_j-x_i-...
user avatar
0 votes
0 answers
16 views

Neighbouring cover in a directed graph

I am not sure if this type of problem has been studied before, so it would be great to receive some guidance. Consider a directed graph G=(V,E). We define an in-neighbourhood cover as a subset $W\...
Andres Fielbaum's user avatar
0 votes
0 answers
8 views

Bipartite Matching With Distant Constraints

I am investigating the complexity of the following problem. Let a complete bipartite graph $G = (V \cup V', E: V \times V')$ with |V| < |V'|, where the nodes have weights $w: V \cup V' \to \mathbb{...
Dom's user avatar
  • 9
0 votes
1 answer
25 views

Recuction from 3-SAT [closed]

Why do we always try to reduce from 3-SAT in order to prove NP completeness? Why 3-SAT in particular? What do we achieve from doing this? Does it have to do with the fact that 3-SAT is NP-complete and ...
luna_98's user avatar
  • 13
0 votes
0 answers
12 views

Is the non-uniform membership problem for sets obtained from 1 by applying affine integer functions P/NP-complete/other?

The question concerns algorithmic complexity of the membership problem for sets obtained from $1$ by applying a fixed number of affine functions. One such example is Klarner-Rado sequence (A002977 in ...
lolicomu's user avatar
0 votes
0 answers
33 views

Real Life Applications of Two-Variable Quadratic Formulas

Where do two-variable quadratic formulas show up today as real-life combinatorial complexity challenges? Weather? Particle motion? Celestial calculations? Routing? Does anyone have specific examples? ...
Schmyndi's user avatar
0 votes
1 answer
39 views

simultaneous subset sum problem and pseudo polynomial algorithm

Given $S \in \mathbb{N}^{q\times n}$ for $q < n $ natural numbers, is there a pseudo-polynomial algorithm which can decide whether exists $x \in \{0,1\}^n$ such that $$ S \cdot x = \begin{bmatrix}...
C Marius's user avatar
  • 1,291
1 vote
0 answers
21 views

NP-Hardness of a Modified Multiple Knapsack Problem

I have $n$ knapsacks, each with a distinct volume capacity denoted as $c_j$. Additionally, there are $m$ items, each with a specified volume $v_i$, where the volume of an item is also equal to its ...
graphtheory123's user avatar
0 votes
0 answers
64 views

NP-hardness of a string transformation problem with k templates

Given strings $x$ and $y$, a template length $l$, and a maximum number of different templates $k$, the task is to determine if it's possible to convert $x$ into $y$ using no more than $k$ different ...
Paul Calvi 's user avatar
2 votes
0 answers
63 views

Efficient proof that a number is NOT a Zumkeller number?

The subset sum problem is known to be NP-complete , so in general there is no efficient method to decide it , in particular to prove a negative result. This problem arises in the problem to decide ...
Peter's user avatar
  • 85.1k
1 vote
0 answers
8 views

Formulating a Spatial Analysis Problem as an NP-Hard Reduction

I'm tackling a computational geometry challenge involving an collection of 2D point coordinates, where each point represents a corner of a polygon. Now I want to fill this polygon with as many points ...
Wismar Günther's user avatar
1 vote
0 answers
76 views

Polynomial Kernel For Minimum Maximal Matching Problem

Let $G$ be a graph, and $k$ be some non-negative integer. The goal is to decide whether there exists a maximal matching in $G$ on at most $k$ edges. This problem is also asked in https://www.mimuw.edu....
Yavuz Bozkurt's user avatar
0 votes
2 answers
123 views

Betweenness problem algorithm counter-example round 2

I asked in previous question about algorithm proof or counter-example. Alex kindly provided a counter-example, I took my time studying it and why it failed producing a valid ordering, so I came with ...
user avatar
1 vote
1 answer
37 views

$2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$ algorithm to break graphs $\mathcal{F}$ in $G$ with vertex deletion.

Let $G$ be any graph. Let $\mathcal{F}$ denote a set of graphs. We say that $G$ is $\mathcal{F}$ free if none of its subgraphs is isomorphic to a graph $f \in \mathcal{F}$. The problem is to delete at ...
Yavuz Bozkurt's user avatar
1 vote
1 answer
39 views

NP-completeness and disjunctions

I have a question regarding NP-completeness and disjunctions. Let $ A ⊆ N^2 $ be an NP-complete problem, and let $ a_1,...,a_n∈N $ be n (dstinct) fixed numbers. Then, in general, can it be said ...
WaLuigi's user avatar
  • 75
2 votes
1 answer
179 views

Betweenness problem algorithm counter-example

Betweenness is an algorithmic problem in order theory about ordering a collection of items subject to constraints that some items must be placed between others. It has applications in bioinformatics ...
user avatar
1 vote
1 answer
112 views

Finding the Crossing number of $K_{4,4}$

I am struggling to find the crossing number of the complete bipartite graph $K_{4,4}$. The best range I can get to is $\text{cr}(K_{4,4}) \leq 16$ (obtained by putting all vertices onto a regular ...
mathy_mathema's user avatar
1 vote
0 answers
27 views

Find a length 100 cycle in an undirected graph is NP Complete?

Given a graph G with N nodes we need to find if cycle of length 100 exists. I've been told that this problem is NP-Complete and can be reduced to the Hamiltonian Cycle problem. I believe this is just ...
nnewtolinux's user avatar
0 votes
0 answers
25 views

solving 3_sat using system of polynomial equations in gf2

Any single variable polynomial in $GF(2)$ is reduced to first degree $x^n=x$. So all polynomials of $n$ variables will be like $x+y+xy$ We can transform any 3-SAT as a system of polynomial equations ...
Mohamed Hamlil's user avatar
2 votes
1 answer
173 views

Choose the "smallest" basis of a set of vectors

First: I know that every basis of some vector space contains the same amount of vectors. The question is not about that. Let $\vec a_1, \dots, \vec a_m \in \mathbb{N}^n \setminus \{\vec 0\}$ be some ...
Moritz Seppelt's user avatar
1 vote
1 answer
40 views

Is this problem on optimizing union of sets NP-complete

Given a collection of sets $C= \{ S_1, S_2, \dots, S_n \}$, is there a subset $S'$ of $C$ such that $|S'| - |\bigcup_{S_i \in S'} S_i| \geq k$? I know that this problem is similar to problems like ...
Lsmith's user avatar
  • 13
0 votes
1 answer
52 views

Resolution Exponential Memory Blowup

I'm looking at the Davis-Putnam algorithm. I don't understand how resolution results in an exponential blowup in the size of the formula, since it seems that after each step, the size is reduced. $(...
David Cheung's user avatar
2 votes
0 answers
73 views

Bin packing : item to be packed in a certain bin depend on previously packed items to that bin.

I am working on an engineering problem. I need to implement an algorithm that looks like a certain variant of bin packing. Specifically, in this variant of the bin packing, the size of a certain item ...
Mazen Ezzeddine's user avatar
-2 votes
2 answers
70 views

Does the idea of creating a perfectly random problem to solve this have any merit, or is it completely useless quackery? [closed]

Statement- If perfect random proves P cannot equal NP Explanation- The crux of P = NP is not figuring out the answer, but rather proving it, and the mathematical community has been approaching this ...
ChadTheVlad's user avatar
2 votes
1 answer
87 views

Reorder a list minimizing the total "distance". Can this unknown problem be reduced to known NP-complete problems?

Working on a pet project I stumbled across an (at least to me) unknown problem which I am not able to reduce to already known and well studied combinatorial problems such as Knapsack or TSP. My gut ...
Ciaccia's user avatar
  • 155
0 votes
3 answers
157 views

Why doesn't a simple equation like this solve P=NP

Can’t we confirm P does not equal np based on simple equations For example this problem will never be solved with an algorithm and can only be solved by guessing (nondeterministic) Problem- You have ...
gggggggggggg's user avatar
3 votes
1 answer
72 views

1-tough non-Hamiltonian graphs

The Petersen graph is a famous example of a 1-tough non Hamiltonian graph, and I stumbled across the following graph which also follows the property: . I found this example in a paper by V. Chvátal. ...
Kian Shah's user avatar
1 vote
0 answers
85 views

NP hardness of bin packing with a fixed number of bins

The general bin-packing problem is NP complete. I have read several papers and other source but I am still not clear about whether a bin-packing problem with a fixed number of bins is NP-hard. ...
Christian's user avatar
2 votes
2 answers
86 views

Is this problem NP-hard?Or what kind of mathematical problem does it belong to?

Assuming there are n types of gifts, each with a number of $a_n$. Now we have to pack them into gift packs, each containing several types of gifts, and each gift has only one.If a gift package ...
ZhuJerry's user avatar
2 votes
0 answers
17 views

Mechanic shop with limited delay capacity

Suppose a mechanic shop serves $M$ customers for $N$ days. Each morning, each customer brings in a number of parts to repair (denoted by $0\leq A_{i,j}\leq A_{max}$). Suppose all parts need to be ...
Andrew Yao's user avatar
0 votes
1 answer
40 views

Does My Conjecture on Selecting 'Special Nodes' in TSP Matrices to Eliminate 97-99% of Edges Hold Potential for Polynomial Time Solutions? [closed]

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove around 97% of the values (weights or distances) that wouldn't ...
Ehsan Javanbakht's user avatar
1 vote
0 answers
44 views

How close to optimal would a Traveling Salesman solution of "Check the distance to all non-visited points, then go to the nearest one" be?

While obviously not optimal, I've usually found that such an "algorithm" is pretty close to the true shortest possible path, and is obviously runnable in polynomial time, with an O equal to ...
Arctic's user avatar
  • 11
2 votes
1 answer
80 views

Minimum connected recoloring on a 6X6 grid with 4 colors.

I've created a small mathematical puzzle involving a 6x6 grid, which has been randomly colored with four distinct colors. The objective is to reassign colors with the fewest changes possible, ensuring ...
Gilad's user avatar
  • 121
2 votes
1 answer
88 views

Is there an algorithm for this variant of the dominating set problem?

I stumbled upon this interesting variant of the dominating set problem lately, and as I have not been able to find a consecrated name, I suppose it has not been thoroughly studied yet. The formulation ...
C. Eyusd's user avatar
6 votes
2 answers
302 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,...
NightShade's user avatar
1 vote
0 answers
38 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 ...
xMath's user avatar
  • 95
1 vote
0 answers
42 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 ...
Anwarul Azim's user avatar
0 votes
0 answers
55 views

Is this discrete optimization problem NP-complete?

Consider a finite set $A \subseteq \mathbb{N} \times \mathbb{N} \times \mathbb{R}$. Minimize $$\sum_n \left( \max_{(n',i,a) \in A, n=n'} (a + x_i) + \max_{(n',i,a) \in A, n=n'} (-a - x_i) \right)$$ ...
braintorture's user avatar
-1 votes
1 answer
65 views

non primitive recursive algorithms having polynomial time verification? [closed]

i think the title speaks for itself, since the defining trait for NP class is that - they are the set of decision problems verifiable in polynomial time by a deterministic Turing machine. thus it ...
user avatar
3 votes
0 answers
42 views

Is Linear Separability of a binary dataset NP-hard?

The Question Is the following problem P or NP? Given a binary datast $\left\{ \left(x_{i},y_{i}\right)\right\} _{i=1}^{\mathcal{O}\left(n\right)},\;x_{i}\in\left\{ -1,1\right\} ^{n},\;y_{i}\in\left\{ ...
Ariel Yael's user avatar
1 vote
0 answers
40 views

P versus NP and the Irreducibility of NP-Complete Problems to P-Complete Problems

If it can be shown that a given NP-complete problem such as Clique cannot be reduced to a given P-complete problem, such as Horn-SAT, then we can conclude that P does not equal NP?
ShyPerson's user avatar
  • 1,730
1 vote
0 answers
11 views

Is Maximizing utility with compliment/substitutes NP

I was trying to code a simple economics simulator where consumers try and maximize their utilities based on a lot of parameters and I think that maximizing utilities is NP-hard but I wanted to ask you ...
SlimeyGuy123's user avatar
1 vote
1 answer
54 views

Prove that the language HAMTWOCYCLES = {G | there exist two cycles in G such that any vertex belongs to exactly one of them} is NP-complete

I have attempted to prove this theorem, but I am not confident in my solution. Can someone please review my proof and let me know if there are any errors, or provide a correct proof if mine is ...
Booker's user avatar
  • 25
3 votes
1 answer
157 views

Take a 3-SAT system and compute its symmetry group, what can we say? How does this group relate to satisfiability?

Take for example, the $3$-CNF system: $$ a \vee b \vee c = 1 \\ d\vee -e \vee f = 1 $$ The symmetry group of the first equation is $S_3 = \langle (x,y) : x, y \in \{a,b,c\}, x\neq y \rangle$ because ...
SeekingAMathGeekGirlfriend's user avatar
0 votes
1 answer
44 views

Is the following Knapsack Variant NP-Hard?

The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
John's user avatar
  • 193
0 votes
1 answer
96 views

complexity classes NP vs. BPP and similar

I do not understand well the relation between nondeterministic class $\mathsf{NP}$ and a probabilistic one, say $\mathsf{BPP}$. Both uses some guesses and random decisions.What is the most direct ...
user122424's user avatar
  • 3,978
6 votes
0 answers
439 views

Is the problem NP-hard?

Let $GF(p) = ({\mathbb Z}_p, +, \times)$ be the Galois field where $p>2$ is prime and let $$ H=\{1,2,\cdots, \frac{p-1}{2}\}.$$ I need an algorithm (subexponential in terms of $\log_2 p$) that ...
qwerty43's user avatar
  • 341

1
2 3 4 5
14