Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
25 votes
3 answers
8k views

Is it really possible to prove lower bounds?

Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use ...
hsalin's user avatar
  • 713
25 votes
2 answers
3k views

Is Logical Min-Cut NP-Complete?

Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
amirv's user avatar
  • 401
24 votes
7 answers
6k views

Justification for neglecting constant factors in Big O

Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
gpuguy's user avatar
  • 1,769
24 votes
3 answers
2k views

Is there a sometimes-efficient algorithm to solve #SAT?

Let $B$ be a boolean formula consisting of the usual AND, OR, and NOT operators and some variables. I would like to count the number of satisfying assignments for $B$. That is, I want to find the ...
Mark Dominus's user avatar
  • 1,525
24 votes
2 answers
4k views

Reduce the following problem to SAT

Here is the problem. Given $k, n, T_1, \ldots, T_m$, where each $T_i \subseteq \{1, \ldots, n\}$. Is there a subset $S \subseteq \{1, \ldots, n\}$ with size at most $k$ such that $S \cap T_i \neq \...
Aden Dong's user avatar
  • 1,121
24 votes
2 answers
337 views

Is Smoothed Analysis used outside academia?

Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?
user avatar
23 votes
5 answers
3k views

P-Completeness and Parallel Computation

I was recently reading about algorithms for checking bisimilarity and read that the problem is P-complete. Furthermore, a consequence of this is that this problem, or any P-complete problem, is ...
Dave Clarke's user avatar
  • 20.1k
23 votes
2 answers
4k views

How is the traveling salesman problem verifiable in polynomial time?

So I understand the idea that the decision problem is defined as Is there a path P such that the cost is lower than C? and you can easily check this is true by verifying a path you receive. ...
wjmccann's user avatar
  • 529
23 votes
3 answers
2k views

Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
GregRos's user avatar
  • 515
23 votes
2 answers
7k views

NP completeness proof of a spanning tree problem

I am looking for some hints in a question asked by my instructor. So I just figured out this decision problem is $\sf{NP\text{-}complete}$: In a graph $G$, is there a spanning tree in $G$ that ...
initialize's user avatar
23 votes
1 answer
1k views

Natural candidates for the hierarchy inside NPI

Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems ...
Mohammad Al-Turkistany's user avatar
22 votes
6 answers
6k views

Is every NP-hard problem computable?

Is it required that a NP-hard problem must be computable? I don't think so, but I am not sure.
Kevin Meier's user avatar
22 votes
3 answers
15k views

HALF CLIQUE - NP Complete Problem

Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please. With that said, here is the problem I am looking at: Let HALF-...
BrotherJack's user avatar
  • 1,115
22 votes
1 answer
2k views

Classification of intractable/tractable satisfiability problem variants

Recently I found in a paper [1] a special symmetric version of SAT called the 2/2/4-SAT. But there are many $\text{NP}$-complete variants out there, for example: MONOTONE NAE-3SAT, MONOTONE 1-IN-3-SAT,...
Vor's user avatar
  • 12.4k
22 votes
1 answer
540 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
Geni's user avatar
  • 321
21 votes
9 answers
9k views

Is Group Theory useful in Computer Science in areas other than cryptography?

I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
Dudi Frid's user avatar
  • 151
21 votes
4 answers
3k views

How hard would it be to state P vs. NP in a proof assistant?

GJ Woeginger lists 116 invalid proofs of P vs. NP problem. Scott Aaronson published "Eight Signs A Claimed P≠NP Proof Is Wrong" to reduce hype each time someone attempts to settle P vs. NP. ...
Isinlor's user avatar
  • 325
21 votes
3 answers
10k views

If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?

Apparently, if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete. Why these two languages in particular? Can't we reduce any other ...
David Faux's user avatar
  • 1,587
21 votes
4 answers
531 views

Complexity classes where $C^C = C$

One possible motivation for studying computational complexity classes is to understand the power of different kinds of computational resources (randomness, non-determinism, quantum effects, etc.). If ...
D.W.'s user avatar
  • 152k
21 votes
2 answers
21k views

Is the open question NP=co-NP the same as P=NP?

I'm wondering this based on several places online that call $\sf NP=$ co-$\sf NP$ a major open problem... but I can't find any indication as to whether or not this is the same as $\sf P=NP$ problem...
Mirrana's user avatar
  • 4,199
21 votes
2 answers
4k views

How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?

In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication. Question : How to prove that it is impossible to ...
Complexity's user avatar
  • 1,157
21 votes
2 answers
5k views

Is the "subset product" problem NP-complete?

The subset-sum problem is a classic NP-complete problem: Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ that sums to $k$? A student asked me if this variant of ...
templatetypedef's user avatar
21 votes
2 answers
830 views

Finding at least two paths of same length in a directed graph

Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$. I would like to know if there are already algorithms for calculating the following decision problem: Are there at least two ...
Paolo Parisen T.'s user avatar
21 votes
1 answer
645 views

Is detecting "doubly" arithmetic progressions 3SUM-hard?

This is inspired by an interview question. We are given an array of integers $a_1, \dots, a_n$ and have to determine if there are distinct $i \lt j \lt k$ such that $a_k - a_j = a_j - a_i$ $k - j = ...
Knoothe's user avatar
  • 458
21 votes
2 answers
5k views

Subset Sum: reduce special to general case

Wikipedia states the subset sum problem as finding a subset of a given multiset of integers, whose sum is zero. Further it states that it is equivalent to finding a subset with sum $s$ for any given $...
ipsec's user avatar
  • 537
21 votes
2 answers
662 views

Problems that provably require quadratic time

I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$. The problem needs to have the following properties: $\Omega(n^2)$ runtime proof for any algorithm - ...
R B's user avatar
  • 2,624
21 votes
1 answer
15k views

Definitions of an algorithm running in polynomial time and in strongly polynomial time

Wikipedia defines it to be An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $T(n) = O(n^...
Tim's user avatar
  • 4,775
21 votes
1 answer
11k views

Easy reduction from 3SAT to Hamiltonian path problem

There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem. Is there a simpler reduction? By simpler I mean a reduction ...
Kaveh's user avatar
  • 21.9k
20 votes
6 answers
7k views

How to prove a problem is NOT NP-Complete?

Is there any general technique for proving a problem NOT being NP-Complete? I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of ...
Untitled's user avatar
  • 981
20 votes
3 answers
686 views

Problems in P with provably faster randomized algorithms

Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \...
aelguindy's user avatar
  • 1,787
20 votes
2 answers
5k views

Can one show NP-hardness by Turing reductions?

In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by ...
user2145167's user avatar
20 votes
3 answers
12k views

How hard is finding the discrete logarithm?

The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$. I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what ...
Matt Groff's user avatar
20 votes
2 answers
537 views

How to scale down parallel complexity results to constantly many cores?

I have had problems accepting the complexity theoretic view of "efficiently solved by parallel algorithm" which is given by the class NC: NC is the class of problems that can be solved by a ...
Raphael's user avatar
  • 71.7k
20 votes
1 answer
4k views

Proving that the conversion from CNF to DNF is NP-Hard

How can I prove that the conversion from CNF to DNF is NP-Hard? I'm not asking for an answer, just some suggestions about how to go about proving it.
jkjk's user avatar
  • 301
20 votes
2 answers
8k views

Difference between time complexity and computational complexity

For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most ...
Median Hilal's user avatar
20 votes
1 answer
8k views

Complexity of Towers of Hanoi

I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments. Is it in NP? Attempted answer: Suppose Peggy (prover) solves the problem & submits it ...
PKG's user avatar
  • 1,489
20 votes
3 answers
344 views

Extension of SQL capturing $\mathsf{P}$

According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe ...
Kaveh's user avatar
  • 21.9k
20 votes
0 answers
661 views

Complexity of deciding whether there is a winning strategy in the following game

The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 \...
frafl's user avatar
  • 2,269
19 votes
3 answers
669 views

For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time?

For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(...
sepp2k's user avatar
  • 1,710
19 votes
3 answers
2k views

Why is the class NP-Complete important compared to NP-hard?

I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-...
Amnestic's user avatar
  • 293
19 votes
2 answers
2k views

A polynomial reduction from any NP-complete problem to bounded PCP

Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something ...
john's user avatar
  • 193
19 votes
2 answers
13k views

PTAS definition vs. FPTAS

From what I read in the ...
M a m a D's user avatar
  • 1,509
19 votes
1 answer
246 views

Decision problem such that any algorithm admits an exponentially faster algorithm

In Hromkovič's Algorithmics for Hard Problems (2nd edition) there is this theorem (2.3.3.3, page 117): There is a (decidable) decision problem $P$ such that for every algorithm $A$ that solves $P$ ...
Raphael's user avatar
  • 71.7k
19 votes
1 answer
1k views

Efficiently computing or approximating the VC-dimension of a neural network

My goal is to solve the following problem, which I have described by its input and output: Input: A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m > n \geq 1$). Output: ...
Artem Kaznatcheev's user avatar
19 votes
1 answer
1k views

Are 'zero-one' jigsaw puzzles NP-complete?

I'm interested in a slight variant of tiling, the 'jigsaw' puzzle: each edge of a (square) tile is labeled with a symbol from $\{1\ldots n, \bar{1}\ldots\bar{n}\}$, and two tiles can be placed ...
Steven Stadnicki's user avatar
19 votes
1 answer
548 views

Proving the (in)tractability of this Nth prime recurrence

As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm ...
MrGomez's user avatar
  • 549
19 votes
0 answers
462 views

Is finding a weight-balanced tree NP-hard?

In the following, we consider binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves. Let $T.l$ and $T.r$ be the left child and ...
rex123's user avatar
  • 316
19 votes
1 answer
2k views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
D.W.'s user avatar
  • 152k
18 votes
7 answers
5k views

Would proving P≠NP be harder than proving P=NP?

Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP. Let Q be one of known NP-hard problems. To prove P=NP, we need to design a single polynomial time algorithm A for Q and prove ...
Kaalouss's user avatar
  • 467
18 votes
4 answers
604 views

Showing that a problem in X is not X-Complete

The Existential Theory of the Reals is in PSPACE, but I don't know whether it is PSPACE-Complete. If I believe that it is not the case, how could I prove it? More generally, given a problem in some ...
Dave Clarke's user avatar
  • 20.1k