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)

1
vote
1answer
117 views

Polynomial-time reduction

How can I prove it? $A \le_p B \Leftrightarrow \overline{A} \le_p \overline{B}$. $A \in \mathcal P \Leftrightarrow \overline{A} \in \mathcal P$. $\overline{A} = \Sigma^* \setminus A$
1
vote
1answer
85 views

Finding a subsequence (of a very long sequence) which does not sum to an even number

[Edited. I've revised to problem to focus on the special case of the integers modulo 2.] You are given a function f from binary strings x ∈ {0,1}n to the integers, or (without loss of ...
0
votes
1answer
262 views

NLogSpace and CoNLogSpace

Assume S1, S2∈ NLOGSPACE. Which of the following statements is true? • S1 \ S2 ∈ coNLOGSPACE • S1 Δ S2 ∈ NLOGSPACE where A\B is the set of members of A that are not members of B. And A Δ B is the set ...
4
votes
1answer
228 views

H-minor free Graph

Recently I cam across a statement which divides graphs into different classes w.r.t. the complexity of problems on them. planar < bounded genus < H-minor free < general graphs My question ...
5
votes
3answers
8k views

Worst case complexity of the quicksort algorithm

Good evening, I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of ...
1
vote
2answers
223 views

Is Turing completeness monotone with respect to Cook reductions?

I think the post title is relatively clear assuming I worded it correctly, but since I was thinking of a specific example: The language of Boolean expressions is Turing complete; Does this imply that ...
3
votes
1answer
175 views

Making sense of the various definitions of computational complexity

I'm a math student and have encountered the concept of computational complexity in several subjects in the course of my studies (numerical analysis, cryptography, intro to computer science and ...
1
vote
1answer
259 views

Complexity of a recursive function

I have a recursive function, and I'm trying to figure out it's complexity. denote P(n) - the runtime of the function (when given the parameter n). I know that : P(n)=n+(n-1)*P(n-1) [p(1)=1] How can I ...
4
votes
1answer
234 views

complexity theory: consequences of P vs NP

I have a basic question regarding the ramifications of P vs NP. If P=NP, then SAT would be in P. If I understand the definitions correctly, this would imply that there is a Turing machine which ...
4
votes
1answer
111 views

How to show that the complexity of a function is $O(\text{polynomial})$

Let $A=\{1,2,4,8,16,32,...,2^k,...\}$, and let $f:A\to \mathbb{N}$ be defined by : $$f(n)=\binom{n}{\log n}=\frac{n!}{(\log n)!*(n-\log n)!}$$ I would like to find out if there exist a polynomial ...
2
votes
1answer
4k views

An algorithm for arbitrage in currency exchange

I found a really interesting problem and I wanted to hear people's opinion. It has to do with currency exchange rate. If we are give some coins $c_1,c_2,\dots,c_n$ and an array $R$ that keeps the ...
10
votes
1answer
340 views

Algorithm for a deck manipulation

Let's say you have a randomised deck of $N$ different cards. An $M$-action ($M\le N$) is defined as follows: you look at the top $M$ cards of the deck, put as many of them as you choose on top of the ...
4
votes
1answer
156 views

Vertex arrangement on the unit sphere

The problem is how can I solve a following in polynomial time? There is a graph $G$ with $n$ vertices, and the goal is to find an arrangement of its vertices on an $n$-dimensional unit-sphere so as to ...
5
votes
1answer
179 views

Primality Testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$?

What is known about the computational complexity of primality testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ where $d$ is a square-free number? For what values of $d$ is primality testing easy ...
3
votes
2answers
165 views

Fast inversion of a triangular matrix

I need to inverse a matrix $A$ given its $QR$ decomposition. It's a numerical task. It is told that the inversion should be "possibly cheap". But it does not look like I can do something more ...
3
votes
2answers
302 views

How do you determine the complexity class of a problem like solving an integral?

The P and NP classes relate to decision problems, but what about more calculation centric problems, specifically solving an integral? How does one figure out if a certain class of integrals is in P or ...
9
votes
4answers
541 views

If $P \ne NP$, is every language not contained in $NP$ $NP$-hard?

The other day, a student asked me whether, if $P \ne NP$, whether any language outside of $NP$ is known to be $NP$-hard. I wasn't sure if This is definitely known to be true, This is definitely ...
2
votes
1answer
124 views

Assuming that SAT is decidable in $2^{O(\sqrt{n})}$, is every language in NP decidable in $2^{O(\sqrt{n})}$?

Assuming that we have an algorithm that decides SAT in $2^{O(\sqrt{n})}$, can every language in NP be decided in that time? I had the following idea: Because SAT is NP-complete, every language in NP ...
0
votes
2answers
82 views

Running times comparison

I am trying to find which of following algorithms has the smallest running time: 1) $O\left(\sqrt{q}\cdot\operatorname{polylog}(q)\right)$; is that linearithmic? 2) ...
2
votes
1answer
755 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
196 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
247 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
489 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
14k 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
634 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
198 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
389 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
195 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
945 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
258 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
199 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
118 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
103 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
112 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
547 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
137 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
221 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 ...
2
votes
1answer
528 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
353 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
468 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 ...