Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
3,667
questions
1
vote
1answer
26 views
Converting a greedy algorithm to a dynamic programming algorithm
Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:
First, find a maximum indpendent set of ...
1
vote
1answer
25 views
Find a truth assignment of 2SAT that has the most number of true variables?
Given a 2SAT instance in CNF where each clause has at most two literals. Let $m$ be the number of clauses and $n$ be the number of variables et let $k$ be a positive number.
Question: Is there a ...
3
votes
2answers
38 views
How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$
In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition
\begin{align*}
\...
-1
votes
0answers
13 views
Polynomial-time algorithm for Clique partition [on hold]
Reductions for showing algorithms. The following fact is
true: there is a polynomial-time algorithm BIP that on input a graph
𝐺 = (𝑉 , 𝐸) outputs 1 if and only if the graph is bipartite: there is a
...
0
votes
0answers
17 views
Do problems that have unary encodings automatically become unary languages?
This problem has confused me a lot, can any of you help me out.
Thank you.
0
votes
0answers
41 views
Confusion about P versus NP [duplicate]
I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
4
votes
1answer
66 views
Are SAT problems with at most one false clause NP-complete?
Is the problem of deciding whether a SAT instance, where at most one clause is false (that is, any given variable assignment will either lead to all clauses being true, or all but one), is satisfiable ...
3
votes
1answer
25 views
Does there exist any unrelativized separation between a quantum complexity class and a classical one?
I'm familiar with results of relativized separation for BPP-BQP, BQP-PH and NPC-BQP. I'm also aware that while e.g. Factoring is not believed to be in BPP, it hasn't been proven and so we're not quite ...
1
vote
0answers
36 views
coloring of an interval graph with constraints
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
1
vote
1answer
29 views
If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete?
The following question was asked on a quiz:
Let S be an NP-complete problem, and Q and R be two other problems (that we don't know much about). If we now know that Q is polynomial time reducible (i....
1
vote
2answers
42 views
Proof with induction even number of letter
I have to proof that in a word $w$ the number of the letter d is always even.
Let $L \subsetneq \Sigma^*$ be a language over the alphabet $\Sigma = \{a,b,c,d\}$
such that a word $w$ is in $L$ if and ...
2
votes
1answer
48 views
Practical hard 3-sat instances
The $3-SAT$ problem is known to be NP-complete problem. Which means that (as far as I understand), unless $P \neq NP$, for every algorithm $A$ which decides $3-SAT$, $A$ runs in super polynomial time (...
2
votes
1answer
32 views
complexity of a variant of the subset sum problem
We have a set of positive integers $N=\{a_1,...,a_n\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$.
What is the ...
0
votes
0answers
26 views
What is the name of this problem (the dual of the asymmetric k-center problem)
I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse.
In this ...
-3
votes
1answer
41 views
I want to solve this question for algorithm, please [closed]
Write an algorithm that calculates the monthly payment of a bank loan with
a fixed interest-rate. Given the principal amount, the fixed interest rate, the number of
years to pay the loan, you can ...
3
votes
1answer
23 views
Prove or disprove that $log^{k}(n) \in O(\sqrt{n}) \forall k > 0$
I'm trying to solve the problem described in the title. By using the free version of wolfram and testing some increasing values of $k$ I get that:
$$\lim_{n \rightarrow \infty} \frac{log^{k}(n)}{\...
2
votes
1answer
29 views
Showing the following language is decidable
Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable.
Generally such questions seem to be ...
1
vote
1answer
18 views
Showing the language of TMs that halt on a decidable set of words is not in RE
I need to show that the following language, L = {$\langle M \rangle$ | The set of words which M halts on is decidable}, is not recursively enumerable. In the instructions they advise thinking of a ...
0
votes
0answers
27 views
Head Position Function of Oblivious Turing Machines
I am trying to understand oblivious Turing machines. According to the book of Arora and Barak, a TM $M$ is oblivious if the location of each of its heads at the $i$-th step of execution on input $x$ ...
-1
votes
2answers
37 views
Time complexity of matrix subtraction
If I have (I-Z) where I is a 3x3 identity matrix while Z is a 3x3 lower triangular matrix, how many subtractions that I should count from this process?
Is it costs K subtractions or (K^2+K)/2 ...
1
vote
1answer
30 views
Pick a random number in a pool with duplicates in O(1) time and less than O(n) space?
Imagine trying to pick a random number from a pool of numbers that contains:
i1 times the number 1
i2 times the number 2
i3 times the number 3
... etc
For example picking a random number in a ...
2
votes
1answer
28 views
Proof on lower bound of search in unsorted array with information theory?
I know there are proofs using an adversary technique. I've seen other proofs for search in a sorted list using information theory. But I haven't come across a proof using it to prove the lower bound ...
5
votes
1answer
56 views
How does $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions?
In the proof of Theorem 1 in this paper by Chen, McKay, Murray, and Williams the authors assume $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ and (in different parts of the proof) state this implies ...
2
votes
1answer
57 views
Is Space Complexity Always Less Than Or Equal To Time Complexity?
Background
I am working on proving a novel problem to be P-Complete, and this requires using a logspace reduction to reduce some known P-Complete problem to the novel problem. Particularly, I am ...
1
vote
1answer
26 views
Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?
NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction.
According to these posts :
Why not polynomial-space ...
3
votes
2answers
35 views
On the hardness of satisfying K number of linear constraints
Background: Normally in linear programing we have some objective function
$$\text{maximize}\sum_{i = 1}^n a_i x_i $$
$$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq ...
0
votes
2answers
39 views
What is the complexity of sum of Logarithm of an arithmetic series
this is the arithmetic series:
$a/b,2a/b,3a/b,...,ba/b$
The new series:
$log(a/b),log(2a/b),log(3a/b),...,log(ba/b)$
I want the complexity of sum of the latter.
p.s: sorry about formatting.
edit ...
5
votes
2answers
123 views
Are there any NP complete problems in SUB EXP TIME?
Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$
Has something like $O(2^\sqrt{n})$ (or any other less than exponential but greater ...
2
votes
0answers
66 views
Set of maximum overlaps
Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap.
I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all ...
0
votes
0answers
29 views
Complexity class of finding a siphon containing a trap?
I have found that finding a minimal siphon containing a set of places in general Petri Net is NP-complete. However, I am curious if this problem lands into a smaller complexity class if we only are ...
1
vote
0answers
22 views
Tape Reduction when T is not time constructible
Arora and Barak showed in their book that we can simulate a $O(T(n))$ time-bounded $k$-tape Turing machine with a $O(T(n)\log{T(n)})$ time-bounded $2$-tape oblivious Turing machine. But it seems that ...
0
votes
1answer
35 views
What are the differences between NP-Complete and NP-Hard? [duplicate]
What are the differences between NP, NP-Complete and NP-Hard?
I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different from what's ...
2
votes
0answers
63 views
Consider vectorization and for loop, do both approaches have the same time complexity?
I am learning this post
Fast computation of nearest neighbors is an active area of research in machine learning. The most naive neighbor search implementation involves the brute-force computation ...
-1
votes
1answer
130 views
Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B
I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219].
Why Isn't this ...
0
votes
2answers
51 views
Runtime complexity of a brute force factoring algorithm? (in terms of bits)
Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
0
votes
2answers
45 views
Reducing from NPC to Co-NPC => NP = Co-NP?
In my lecture we learned:
If X is NPC and X in Co-NP => NP = Co-NP
Would it be enough to prove NP = Co-NP if I reduce a ...
2
votes
2answers
111 views
How to prove NP-hardness from scratch?
I am working on a problem of whose complexity is unknown.
By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use.
Finally, I have decided ...
5
votes
2answers
130 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 ...
4
votes
0answers
40 views
Convex quadratic approximation to binary linear programming
Munapo (2016, American Journal of Operations Research, http://dx.doi.org/10.4236/ajor.2016.61001) purports to have a proof that binary linear programming [1] is solvable in polynomial time, and hence ...
1
vote
2answers
45 views
Can you have simple unit tests for complicated function? [closed]
Can you have simple unit tests for complicated function?
For example: Turing test for AI.
Do you always can find simple unit tests for any complicated enough function / algorithm?
1
vote
0answers
17 views
Complexity classes for various models of computation
The various complexity classes usually taught and studied ($P$, $NP$ $co-NP$, EXP, NSPACE etc) are usually defined using Turing Machines as the preferred model of computation.
Are these sets of ...
1
vote
0answers
37 views
C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?
I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments.
The algorithm iterates over every edge in the graph.
...
1
vote
0answers
68 views
Minimum path cover in a DAG
Given a directed acyclic graph $G=(V,A)$ and a set $A'$ of $A$. It is well known that searching for a minimum number of vertex-disjoint paths that cover all the vertices of $G$ can be solved in ...
4
votes
0answers
125 views
Is this equivalent to any famous NP-complete problem?
Given the following problem.
Given an $n\times n$ matrix $A := \{a_{ij}\}$. Find an $n\times n$ matrix $X := \{x_{ij}\}$, where $x_{ij} \in \{-1, 1\}$ for $i, j \in [n]$, that minimizes the ...
3
votes
1answer
69 views
Algorithm to find a simple path with maximum weight less than a constant in DAG
Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...
3
votes
3answers
95 views
Is it possible to have high compression but low predictability?
Can you have a process that generates a binary sequence with high compression rate (low entropy) but impossible to predict next symbol?
'impossible to predict' - sequence cannot be predicted ...
0
votes
0answers
31 views
If two languages are reducible to the same third language, are they necessarily reducible to one another?
Speaking of polynomial time reductions.
1
vote
1answer
25 views
Complexity analysis using big - O, Omega and Theta notation
I was reading a research paper and there I read the following:
$t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\...
3
votes
1answer
116 views
Minimum Path cover in a Directed Acyclic Graph
Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-...
2
votes
1answer
55 views
Doubts about Baker-Gill-Solovay
How am I supposed to read the P=?NP relativization proof? I am reading the classical paper Relativization of the P=?NP problem by Baker, Gill and Solovay, in particular the proof that there exist an ...
