All Questions
Tagged with complexity-theory optimization
145 questions
1
vote
0
answers
49
views
Data structure for tracking boolean clauses size
Given an unordered sequence of n boolean conjonction clauses which may contain duplicates, I am looking for a data structure that would track the number of clauses grouped by the number of variables ...
- 11
1
vote
1
answer
61
views
Is this graph grouping problem $\mathsf{NP}$-hard?
Let's introduce the notion of layer: given a simple graph $G$ a layer is a subgraph of $G$ satisfying the following property:
If any pair of vertices is connected with an edge, these two vertices ...
- 2,041
5
votes
0
answers
117
views
Minimum cost path connecting exactly K vertices
I came across a situation in real life that maps to this optimization problem:
Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ ...
- 51
2
votes
2
answers
118
views
No Neighbor Vertex Cover
Let $G=(V,E)$ be an undirected connected graph with a set of vertices $|V|$ and a set of edges $|E|$. A set cover $D$ satisfies $D \subseteq V$ and $uv \in E \implies u \in D \lor v \in D$. A variant ...
2
votes
2
answers
443
views
Algorithm that generates verification program from solution program of NP problem
I don't know complexity class theory well so I might make some categorical errors, but I will try to ask this question anyways.
Suppose you have written a function in some programming language which ...
- 121
0
votes
1
answer
60
views
Minimizing the number of distinct elements by picking one set from each set of sets
I have a problem as follows. Given a set of sets $U = \{S_1, S_2, … S_N\}$ where $S_i = \{s_1, s_2, ... s_m\}$. Each $s_j \in S_i$ contains a set of distinct elements. I need to pick one $s_j \in S_i$ ...
- 141
1
vote
1
answer
169
views
Reduction from MAX-3-CUT to MAX-CUT
Both MAX-CUT and MAX-3-CUT are known to be NP-complete. This post shows a reduction from MAX-CUT to MAX-3-CUT. I am curious if there is a way to reduce MAX-3-CUT to MAX-CUT?
MAX-CUT: Given an ...
- 113
0
votes
1
answer
22
views
NP-HARD optimization problem and instance correlation
If an optimization problem A is NP-hard and P≠NP, then does there exist an instance x of A such that no polynomial algorithm provides an optimal solution for x?
1
vote
1
answer
118
views
NP-Complete Proof - Using CFLP
I have formulated the below optimization problem.
\begin{align}\nonumber
\hspace{-3mm}&\text{(P) minimize}\!\sum_{i}\!\alpha_{i}w_{i}\!+\!\sum_{i}\sum_{j}\!c_{ij} p_{ij}\!\\
\text{s.t.} & \...
- 15
1
vote
1
answer
105
views
Integrality gap and complexity classes
I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems?
In particular, is there a class of problems for which their integrality ...
- 269
2
votes
0
answers
167
views
Can protein folding destroy cryptography?
They say that protein folding is an NP-hard problem, meaning that if we could figure out how any protein folds, we could solve any NP problem in polynomial time. However, doesn't this basically ...
- 97
1
vote
1
answer
57
views
Class of optimization problems whose decision versions are in P
NPO is defined to be the class of optimization problems whose decision versions are in NP.
I would like to get the complexity class of optimization problems whose decision versions are in P.
Is such ...
- 269
3
votes
0
answers
126
views
Is there a class for optimization problems with polynomial-time-computable bounds?
An optimization problem can be described by two functions $f$ and $g$, such that:
$f$ is a binary predicate representing the constraints: $f(x,y)$ is True if the output $y$ is feasible for the input $...
- 6,164
1
vote
2
answers
438
views
Can the optimization version of a problem be NP-hard while its decision version is in P?
I have formulated an instance of a 0-1 Integer Program (IP), which I am trying to determine the complexity of (can this instance be solved in polynomial time or not). As we know, the 0-1 IP is NP-...
0
votes
1
answer
191
views
Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?
Let's say that we have a decision problem $P$. Let's also say that $I_n$ is the set of all instances of size $n$ that exist for this problem, and that its cardinality is finite.
There is a sequence of ...
- 145
0
votes
0
answers
39
views
Finding the Optimal Palette for a Set of Images
Motivation
I want to draw pictures using indexed colors. As I have limited space for colors per-palette, I want to choose palettes in an intelligent fashion, based on the pictures I want to draw. The ...
- 1
1
vote
1
answer
181
views
What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?
I'm trying to figure out a more efficient solution to the following problem.
Dataset: A set of arrays of key-value pairs (K, V). The arrays have varying lengths, ...
- 111
1
vote
1
answer
158
views
What is the name of the complexity class for the optimization version of co-NP-complete and coNexpTime-complete problems?
I know that the optimization version of NP-complete problems belong in NPO. What about co-NP-complete problems? Is there a co-NPO class, or is it just NPO?
I've also never seen the name for the ...
- 23
2
votes
0
answers
32
views
How can we reduce the spatial complexity of intermediate indexes in relational databases at execution time?
In relational databases, what are the practical or theoretical ways to reduce the size and spatial complexity of intermediate indexes or tables* at execution time (so for example to reduce the size of ...
- 21
1
vote
1
answer
247
views
Complexity of Nelder-Mead Algorithms
If the objective function contains $n$ variables (e.g. $f(x_1, ..., x_n)$) in the Nelder-Mead algorithm (or other direct search methods), is there any known lower/upper bounds on how many times the ...
- 123
3
votes
1
answer
172
views
A complexity class between P and FPTAS
The question is about approximation algorithms to NP-hard optimization problems.
For concreteness, let $M$ be a minimization problem with $n$ inputs, where all inputs and outputs are integers in the ...
- 6,164
1
vote
1
answer
188
views
Independent set problem with given black box
I'm very new to P and NP complexity classes and reductions. I'm trying to solve this problem and I want to verify my solution and if it is wrong, understand why.
Suppose that I'm given a polynomial ...
- 15
1
vote
2
answers
80
views
Determine the time complexity of repeated logarithm until not greater than 1
t <- n
while t>1 do
t <- log_2(t)
I tried to do it this way:
$f^\text{(1)}(t)=\log_2(t) \\ f^\text{(2)}(t)=\log_2\log_2(t) = \log_2^{(2)}(...
- 145
1
vote
0
answers
41
views
NP-hardness proof of an optimization problem with real values and real input in the decision problem
Question - Let's suppose we have an optimization problem $\mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $\mathcal{P}_D$ (please see definitions ...
- 41
1
vote
0
answers
39
views
Approximation classes for optimization problems with real values
Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.?
If my understanding is correct a ...
- 41
2
votes
0
answers
116
views
NP-hardness proof of an optimization problem with real values and rational input in the decision problem
I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated.
For the question, take the ...
- 41
3
votes
1
answer
184
views
Merging Tuples of Intervals
Suppose I have a list of tuples. Each tuple contains 2 intervals. The intervals in each tuple have nothing to do with each other. I would like to find a smaller list of tupels that covers all elements ...
- 63
3
votes
1
answer
219
views
Polynomial time optimization problems belong to which complexity class?
I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can ...
- 6,267
3
votes
0
answers
78
views
Minimum Vertex Cover of 2 vertex disjoint odd cycles that have edges between them
Consider the graph $G$, which is comprised of 2 vertex disjoint odd cycles ($C_1$, $C_2$) where $|C_1|$ and $|C_2| \geq 5$. $G$ is sub-cubic and connected, with edges in between the cycles. Because $G$...
- 31
2
votes
1
answer
295
views
Efficient algorithm to compute the diameter of a convex set?
Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the ...
- 23
1
vote
0
answers
35
views
Measure divergence in Particle Swarm Optimization
I'd like to monitor divergence/diversity in my swarm during the particle swarm optimization algorithm to measure when the swarm search space is converging.
This would be used as one metric to be ...
- 121
1
vote
1
answer
168
views
Must an optimization problem with a greedy algorithm belong to P?
If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the ...
- 143
1
vote
0
answers
40
views
Connection between convergence complexity of gradient descent and complexity of exactly solving convex program?
Let $f: \mathbb{R}^n \to \mathbb{R}$ be a convex function. Let $V \subseteq \mathbb{R}$ be some closed convex set. Consider the following convex minimization problem:
\begin{align}
\min_{\mathbf{x} \...
- 23
2
votes
2
answers
51
views
Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem
I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following:
There exists a believed-today NP-hard problem ...
- 529
3
votes
1
answer
447
views
Approximation factor preserving reduction
The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365:
Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving
...
- 143
2
votes
0
answers
465
views
Minimum vertex cover and odd cycles [closed]
Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $...
1
vote
1
answer
104
views
Maximization problem on finite collection of finite sets
Problem
I am considering the following maximization problem:
Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$.
Goal is to find a subset $G \subseteq \mathcal{F}$...
- 123
2
votes
0
answers
71
views
An optimization version of 2QBF: is it $\mathsf{NP}^{\mathsf{NP}}$-hard?
I am studying the computational complexity of the following decision problem related to 2QBF:
Input: a 3-CNF formula $\varphi$ over $X \cup Y$, where $X$, $Y$ are disjoint sets of propositional ...
- 95
5
votes
1
answer
91
views
Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope
I want to solve a linear programming problem in the $2n$ variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ where the cost is of the form $x_1/y_1 + \cdots + x_n/y_n$. Specifically, I want to solve
\...
- 171
1
vote
0
answers
52
views
shortest string containing all binary palindrome of length n as substring
I am trying to compute the shortest binary string that contains all binary palindrome of length n as substring. For example, for n=3, 00010111 is such a shortest string. However, brutal force performs ...
- 231
1
vote
1
answer
214
views
Reframing decision, counting, enumeration, and search as optimization
The top accepted answers to the questions below allude to two complexity classes of optimization problems: NPO and PO (in relation to NP and P for decision problems):
Decision problems vs "real" ...
1
vote
1
answer
81
views
How does the length of the output of a problem inform its complexity?
Consider the decision problem: Subset sum. For an input set of integers, it asks for a Yes/No answer to the question of whether or not we can find a subset of elements of this input that add up to 0. ...
- 316
1
vote
0
answers
35
views
Complexity of maximization of entropy of Hamming distance of bitstrings
We have a set of possible "key"s $S$ represented by bitstrings of length $k$. In other words, $S$ contains an arbitrary subset of all bitstrings of length $k$. For example, when $k=3$, it can be $S = \...
- 1,101
3
votes
0
answers
80
views
Calculating number of intersections of a horizontal line with line segments efficiently
I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$.
Now, I'm given $q$ queries in the form of $...
- 115
-1
votes
2
answers
79
views
Question about epsilon and estimation Turing machines
i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
- 1
2
votes
0
answers
32
views
Looking for some references on voting theory
After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 ...
- 21
4
votes
0
answers
38
views
Strongly connected subgraph that contains no negative cycles
Is there an efficient algorithm that solves the following decision problem:
Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
user113863
0
votes
0
answers
35
views
Why does such reductions work [duplicate]
In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS)
$V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$
The ...
- 222
0
votes
0
answers
22
views
is the complexity of an algorithm connected to the "classification" of a optimization problem?
I wonder if the complexity is connected to an optimization problem. In general but also specifically e.g. when having a look at $ O(n^2) $. Does this just describe the complexity in general or does it ...
- 113
9
votes
2
answers
3k
views
If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?
Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.
Now I am learning that a convex optimization problem can ...
- 623