Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

2
votes
1answer
748 views

Prove the following: if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(h(n))$ then $f(n)$ is $O(h(n))$

I understand that $f(n) \leq Ng(n)$ and $g(n) \leq Nh(n)$ so obviously $f(n) \leq Nh(n)$, but how would one go about proving this using proper semantics (using big $O$ notation)?
2
votes
1answer
190 views

Complexity of Gauss elimination over ring $Z_n.$

Is there some polynomial upper-bound for Gauss elimination over ring $Z_n$? I'm interested in polynomial bound depending from size of matrix and $\log n$. I also have the same question about the ...
4
votes
1answer
246 views

Is there any decidable problem that is NOT NP-HARD?

Is there a proof that there exists a decidable problem that is NOT NP-HARD??
3
votes
2answers
186 views

Method of Modeling Problem Complexity

Is there a standard way to model the complexity of a mathematical problem? If so, what are the best online resources to learn more about it? Honestly don't have an even a basic way to model the ...
7
votes
2answers
476 views

Do there exist exponential-time problems, even if $P=NP$

Can we say that there are some problems that take exponential time even if $P=NP$ For instance problems like: enumerating all spanning trees of a graph, enumerating all hamiltonian paths of a graph, ...
2
votes
2answers
13k views

What is the 3SAT problem?

I don't get the 3SAT problem. Can someone explain the 3SAT problem as if I were 5 years old, ideally with examples? Thanks!
0
votes
1answer
624 views

Is this partition problem strongly NP-complete?

The Partition problem is weakly NP-complete: Given a set A of positive integers, can A be partitioned into two disjoint subsets with the same sum? I'm interested in the hardness of this variant: ...
1
vote
1answer
193 views

Many-One Reductions vs Turing-Reductions and PH

One definition of $\mathsf{PH}$ uses Oracles and in this definition both $\mathsf{NP}$ and $\mathsf{coNP}$ are contained in P^NP which equals $\mathsf{P^{coNP}}$. It is believed that $\mathsf{NP}$ ...
1
vote
2answers
381 views

Number Partitioning with Cardinality Constraint: Is that NP-Hard?

Given a set of integers $S=\{a_1, \dots, a_n\}$ where $a_i > 0$ and $n$ is an even number, we want to find $A \subset S$ so that: $$ \left| \sum_{a \in A}a - \sum_{b \in S-A}b \right| $$ is ...
1
vote
1answer
57 views

Reduction over Exactly $m$ models

Let introduce the "Exactly $\{m_{1},m_{2}\}$-SAT" problem : Given a CNF formula $F$ and $2$ integers $m_{1}$ and $m_{2}$, is it true that $F$ has exactly $m_{1}$ or $m_{2}$ models ? I guess Exactly ...
0
votes
2answers
192 views

Complexity of sorting algorthms

I've read an article (German) about different sorting algorithms where the author states this: [Smoothsort] is a sorting algorithm that uses swaps to sort and does not need any extra external ...
9
votes
1answer
5k views

Computational complexity of least square regression operation

In a least square regression algorithm, I have to do the following operations to compute regression coefficients: Matrix multiplication, complexity: $O(C^2N)$ Matrix inversion, complexity: ...
5
votes
4answers
921 views

Does DTIME(O(n)) = REGULAR?

(I don't think that this is a good fit on cstheory, since I figure that this question already has a known answer. However, if you think that this would be a better fit there, please feel free to ...
10
votes
2answers
257 views

An interesting way of producing positive integers

If we define $$\cal N _1 := \{ 1\} $$ and by induction $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$ it's easy to prove that, for every $m ...
2
votes
0answers
180 views

Complexity of finding all edge cuts of a directed graph

I have a problem in which for a certain graph I need to compute the min cut for r times (r can be HUGE). Because each time the edge weights can be different, what i am doing (in practice) is to ...
1
vote
1answer
58 views

Argument about reduction from $\Sigma_{i+1}^p$ to $\Pi_{i}^p$

We know that the satisfiability problem for a formula in the form of $\exists x_0 \forall x_1 \exists x_2 \ldots Q_i x_i . \phi(x_0, \ldots, x_i)$ is complete for $\Sigma_{i}^p$, where $Q_i$ is a ...
2
votes
0answers
115 views

Complexity of map coloring

This is a follow up question to this one. I've recently read that for planar maps, it is possible to color these in $O(N^2)$, $N$ being that number of vertices [1]. What are the computational ...
2
votes
2answers
1k views

Is coNP closed under Kleene star?

Is coNP closed under Kleene star operation? I have the answers, in which they say it is possible to build a graph that describes all possible divisions of the string in which the sub-words are in in ...
2
votes
1answer
99 views

Is it possible to remove exactly one solution from a CNF in polynomial time?

Given a conjunctive normal form (CNF) is it possible to remove one solution from its set of solutions (irrespective of whether the CNF has a solution or not in the first place)? By that I am asking if ...
0
votes
1answer
175 views

Levels of abstraction in computational complexity

At college years ago, I enjoyed the course on theoretical computer science. But there was something that always bugged me about the results: results were always listed with regards to some O(n) of a ...
1
vote
1answer
111 views

NP-hard problems which are easy on average

Are there any known NP-hard problems that are easy on average as per the definition of average-case complexity by Levin?
1
vote
2answers
543 views

Counting inversions in lists algorithmically

I want to extract useful info from some data and this makes me think how to do it efficiently. I will try to explain the problem with math terms. If we have a sequence of numbers $A=(a_{1}\space ...
1
vote
0answers
136 views

Counting Bipartite Matchings and Satisfiability

Counting the number of bipartite matchings is #P-hard. Thus every #SAT problem can be reduced to counting the number of bipartite matchings. If a SAT problem is unsatisfiable however, it will have 0 ...
1
vote
1answer
120 views

How to continue this argument/proof?

I was wondering to myself what the actual run time of Mergesort was, so I thought like this: We have the sort operation that takes time $s(2) = 1$ and $s(1) = 0$. Merging two sorted sequences with ...
2
votes
2answers
99 views

Which oracles does Relativization apply to?

In 1975, Baker, Gill, and Solovay presented a landmark paper on Relativizations of the P ?= NP question. My question is fairly simple. Does their theory hold for all oracles? I ask this because I'm ...
3
votes
1answer
220 views

Regular expressions which first disagree after an exponential length

Problem 8.24 of Sipser's Introduction to the Theory of Computation asks: For each $n$, exhibit two regular expressions $R$ and $S$ of length $poly(n)$ where $L(R)\not =L(S)$, but where the first ...
1
vote
1answer
513 views

How is HORNSAT equivalent to 2SAT?

I rises this question because I read Tim's question "Why are Hornsat, 3sat and 2sat not equivalent?" Quoting him: "... This new problem though is polynomial time equivalent to a certain instance of ...
2
votes
1answer
351 views

co-NP assertion

I want to prove that the below assertion is false: Given L1,L2 $\in$ co-NP, does L1 $\cap$ L2 $\in$ NP ? I already know that co-NP is closed under intersection and union, but this result is not ...
2
votes
3answers
467 views

Fake Proof that $\mathrm{NP}^\mathrm{NP} = \mathrm{NP}$

I found this faulty proof of $$ \newcommand{\NP}{\mathrm{NP}} \NP = \NP^{\NP}, $$ where the tricky part is to proof that $ \NP ^{\NP} \subseteq \NP$, and this is how it is realized: Take $\NP^\NP$ ...
1
vote
0answers
86 views

Solving a non-linear inequality related to geometric Brownian motion

Consider the non linear inequality $$\sum_{i=1}^{n}a_{i}u^{\sum\limits_{j=1}^{i}y_j} > c$$ $$y_j \in \{0,1\}, j=1,2,\dots,n$$ $$a_i \in \mathbb{R}, i=1,2,\dots,n$$ $$n \in \mathbb{N}, u>0, c ...
3
votes
4answers
2k views

The tricky time complexity of the permutation generator

I ran into tricky issues in computing time complexity of the permutation generator algorithm, and had great difficulty convincing a friend (experienced in Theoretical CS) of the validity of my ...
2
votes
1answer
474 views

Proof that a multiplication verification can be done in log space

In Sipser's Introduction to Theory of Computation, he asks us to show that the language $MULT=\{(a,b,c):ab=c\}$ with $a,b,c\in\mathbb{Z}^+$ can be decided in log space. I originally started out with ...
0
votes
1answer
149 views

Merlin-Arthur complexity class for function problems

Quoting wikipedia, the complexity class $MA$ is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol where Merlin's only move precedes any computation by ...
5
votes
2answers
370 views

Is there a log-space algorithm for divisibility?

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...
1
vote
1answer
89 views

Size of an NL TM

On page 325 of Sipser, he gives a proof that PATH is NL-Complete which says basically that we can create a graph where each node is a configuration of a TM, and then solving if a path exists ...
0
votes
1answer
94 views

A special case of the minimum number of multiplications used to compute a product of matrices

A fact about complexity of algorithms for computing the product of matrices was brought up to me that was very interesting I was not aware of. I still am not sure what the optimal bound is on the ...
6
votes
3answers
338 views

How complicated is the set of tautologies?

Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$. How ...
1
vote
2answers
65 views

Proof of a lower bound $\lambda(n)$ of the smallest number of multiplications $\ell(n)$ needed to compute $a^n$ for an integer $a$

Let $\ell(n)$ be the smallest number of multiplications needed to compute $a^n$ for any integer $a$. Here, a multiplication is $a_i := a_j \cdot a_k$ for $j, k < i$ and $a_0 := a$, e.g. $\ell(8) = ...
0
votes
1answer
43 views

Prove non-equivalence with Big Omega

How to prove non-equivalence of this? $a^n = \Omega(b^n)$ when $0 < a < b$
0
votes
1answer
261 views

Finding a Big-O notation of: $\sum\limits_{i=1}^{k} ( t(a_i n)) + n$

I'm trying to find a Big-O notation of: $\displaystyle\sum_{i=1}^{k} ( t(a_in)) + n$, where $\displaystyle\sum_{i=1}^{k} (a_i) < 1$ using a recursion tree method and substitution method. I've ...
1
vote
0answers
355 views

Complexity of divide and conquer algorithms?

I have two datasets with $n$ and $m$ points. To find the match I have to compare each point in one data set with the other data set which makes the complexity $O(m\times n)$. I did some heuristics and ...
3
votes
1answer
273 views

Solving a maze by taking a random walk

I vaguely recall a result like the following from one of my complexity theory classes in school: given a 2d maze (which I guess we can think of as a directed graph with a fixed start node and exit ...
2
votes
2answers
927 views

Factoring n, where n=pq and p and q are consecutive primes

So in RSA, there is a modulus n which is the product of two primes. My question is regarding when p and q are consecutive primes, what would the time complexity be? So, n=pq and p and q are ...
4
votes
1answer
270 views

Is quadratic reciprocity problem in coNP?

Quadratic reciprocity is in $\mathsf{NP}$, since to prove $x$ is quadratic residue you can show $y$ such that $y^2=x$. Wikipedia claims the problem is in $\mathsf{coNP}$. This book claims it is not ...
2
votes
2answers
353 views

Confused about Wikipedia definition of NP

I've been checking my understanding of the definitions of NP and NP-complete and I am confused by some of the definitions given on Wikipedia; for example, the article about NP-complete describes NP ...
0
votes
1answer
279 views

Is it correct to say that $P=NP$ implies $P=NPC$?

Is it correct to say that $P=NP$ implies $P=NPC$? I was reviewing the definition of NP-complete and I noticed this diagram which states that if $P=NP$, then $P=NP=NPC$. However, it seems to me that ...
1
vote
1answer
146 views

Reduction over intersection of languages

Given two languages $L1$ and $L2$, such that $L2$ is NP-Hard under polytime (many-one or Turing) reduction. Let $L=L1\cap L2$. 1- Is it true that if $L2$ is polytime (many-one or Turing) reducible to ...
2
votes
0answers
279 views

Proving that basic linear algebra problems (LINEQ and Linear Programming) are in NP

I'm working through the problems in Arora & Barak's textbook on Computational Complexity. It's all been good so far, but I'm kind of stuck on this pair of problems in Chapter 2 (2.3 and 2.4). I'm ...
3
votes
1answer
590 views

Find the subset of a graph that has the highest minimum spanning tree benefit and a total edge weight within some threshold

Suppose we have a graph $G$ = ($V$, $E$) where each vertex $v_i \in V$ has a benefit $b_i$ and each edge ($v_i, v_j$) $\in E$ has a weight of $w_{ij}$. I would like to find a subgraph of $G$ that ...
2
votes
1answer
88 views

Puzzle: Generate the Highest Bounded Number Using a Limited Number of Characters

A friend and I were sitting in our cubes at work and trying to create the greatest bounded number we could using only a few characters. We came up with $A(G,G)$, which is the Ackermann function with ...