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)

0
votes
0answers
3 views

Cycle of length k with no repeated edges

I need to figure out what is the minimum complexity class (L, NL, P, NPC etc..) of the following problem: Given an undirected graph G, is there exist a cycle (doesn't have to be a simple cycle) with ...
2
votes
1answer
19 views

What's the meaning of “reuse space”?

I'm reading this. $\quad \;\;$ What's the meaning of reuse space in here?
1
vote
3answers
20 views

Prove of a Landau-equalities

I have to prove or disprove the following Landau-equalities: $$ O(f+g) = O(max(f,g))$$ and $$O(f-g) = O(min(f,g))$$ with $f,g: \mathbb N \to \mathbb R^+$ . To show equality of two sets, one has to ...
1
vote
1answer
19 views

Computational complexity comparison between MINLP and MILP

Can someone please explain the computational complexity of MINLP and MILP, though both are NP-Hard. What is the advantage of having an MILP formulation over MINLP formulation for a same optimization ...
1
vote
1answer
40 views

Expected time of Quicksort

I am reading the proof of the theorem: The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time. The proof is this: For simplicity in the timing analysis assume ...
0
votes
1answer
13 views

Time complexity comparison between two functions

I'm confused as to how $f(n)$ can be $O(g(n))$, $\Theta (g(n))$ and $\Omega(g(n))$. Could someone help explain?
1
vote
1answer
22 views

Las Vegas Algorithms

In some notes i'm reading it says that the definition of a Las Vegas Algorithm is An algorithm which always outputs the correct answer but has unbounded running time, with the expected running time ...
5
votes
1answer
40 views

Choosing primes uniformly at random

I'm interested in efficient methods of generating prime numbers in a given range [a, b] (or with a given number of bits/digits, etc.). By "efficient" I mean minimizing time, randomness, and perhaps ...
1
vote
1answer
23 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
1
vote
3answers
30 views

What is the growth rate of the logarithm of the factorial sequence?

I'd like to know the space complexity of storing bit string representations of the numbers in the factorial sequence (as in a memoized factorial function). So each number $f_i=i!$ in $i=0 \cdots n$ ...
0
votes
2answers
35 views

Proof NP-Complete for $L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$

$L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$ and I try to prove it's NP-Completeness. It seems really easy since obviously it is at least as hard as HAM-PATH which is ...
0
votes
0answers
20 views

Is there a universal constant for size of disjoint clauses in 3-CNF

We are given a 3-CNF formula $\Phi$ on n variables, and a guarantee that at least 1% of $2^n$ possible assignments satisfy all clauses in $\Phi$. Now construct set $S$ of disjoint clauses so that no ...
1
vote
2answers
48 views

Are there undecidable problems for which a solution has been found?

I mean are there examples of problems that have been proven to be undecidable, in the sense that it would not be possible to devise a deterministic computer program that outputs a solution for an ...
0
votes
2answers
25 views

Can a function exist that is both $o(g(n))$ and $\omega(g(n))$?

Can a function exist which is both $o(g(n))$ and $\omega(g(n))$? Wouldn't this imply $$m |g(n)| \le |f(n)| \le k |g(n)| $$ If $f(n) = g(n)$ then wouldn't an arbitrary integer $m$ be greater ...
0
votes
2answers
76 views

Proof of a Landau-inequality

I have to prove or disprove the following: $$ 2xlog_{10}((x+2)^2) + (x+2)^2log_{10}(\frac x2) \in O(x^2log_{10}(x))$$ My approach (with $log$ is meant $log_{10}$): $4x log(x+2) + (x+2)^2log(x) - ...
1
vote
0answers
29 views

Complexity of combination method

I have a question about complexity of combination two methods. Assume that I have method A with its complexity is $O(n)$ and second method that has complexity is $O(n^2)$. In which, n is number of ...
3
votes
2answers
1k views

what is the computational complexity of solving a quadratic program with linear inequality constraints

I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
3
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 ...
9
votes
1answer
4k 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: ...
0
votes
2answers
31 views

Find both the largest and second largest elements from a set

Consider finding both the largest and second largest elements from a set of $n$ elements by means of comparisons. Prove that $n+\lceil \log n \rceil -2$ comparisons are necessary and sufficient. ...
0
votes
1answer
16 views

complexity question regarding whether it is decision problem

When self teaching complexity theory and seeing arguments that were made online. I get some confusion. In the class, we classify problems into P: can be computed polynomially NP: given a claimed ...
0
votes
1answer
29 views

NP-completeness of Ising model

In this paper: http://www.brown.edu/Research/Istrail_Lab/papers/p87-istrail.pdf It is claimed that calculating partition function of 3 dimensional ising model is NP-complete. But I have a question, ...
1
vote
0answers
80 views

smallest circuit

Let $SMALLESTCIRCUIT$ be the language consisting of all Boolean Circuits $C$ with the property that there is no smaller circuit $C^{'}$ that has the same truth table as $C$. (smaller means having ...
0
votes
1answer
32 views

checking boolean logical equivalence

Given two boolean formula (aka. logic circuit), I want to check if they are logically equivalent, namely that they compute the same truth table. Is this an NP-complete problem? What is the proof?
0
votes
1answer
291 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
2
votes
2answers
64 views

Efficiency of a max-min problem for $\sum_{j=1}^m |b_j-a_j|$ with $a_i$, $b_j$ restricted to convex sets

Consider the following optimization problem: $$\max_{\{a=(a_1,a_2,\ldots,a_m)\in A\}}\min_{\{b:=(b_1,\ldots,b_m)\in B\}} \sum_{j=1}^m |b_j-a_j|.$$ Is computing the optimal value of this problem ...
7
votes
1answer
814 views

If an unary language exists in NPC then P=NP

I've a question regarding a theorem in Complexity Theory. It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct. It means that there exists ...
0
votes
2answers
24 views

3-COLOR Decision Problem

The 3-COLOR problem takes as input a graph and decides whether it can be colored using only 3 colors so that no 2 adjacent nodes have the same color. The reduction from 3-SAT to 3-COLOR uses the ...
0
votes
0answers
6 views

QBF - space complexity in detail

As I'm new to the "complexity theory" stuff I've some trouble with proofs which are "obvious" regarding all books I've found so far. In this case I want some evidence why a certain algorithm has space ...
1
vote
1answer
63 views

Understanding the complexity class $P^O$ for randomized oracles

We know from Toda's theorem that $PH \subseteq P^{PP}$. What do we know about the following classes? $$ P^{ZPP}, P^{RP}, \text{ and } P^{BPP} $$
0
votes
0answers
10 views

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$. A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} ...
0
votes
1answer
28 views

Calculating $b_1,b_2,…,b_k$ where $b_i$=$a_1a_2…a_{i-1}a_{i+1}…a_k$ in minimal number of multiplications

Let's suppose we have a set of integers $a_1, a_2, ..., a_k$ in $Z_n^{*}$, and that we define $b_i$ to be the multiplication $a_1a_2...a_{i-1}a_{i+1}...a_k$. Is there a way to calculate the set ...
-1
votes
2answers
36 views

Big-Oh and limits proof?

Prove or disprove: $2^n$ is in $O(3^n)$. I know I have to use some calculus limit techniques but I can't seem to get anywhere. Steps and an approach would be helpful, especially confirming if this has ...
1
vote
0answers
21 views

Computation Complexity POLYLOGSPACE

POLYLOGSPACE is the complexity class $ \bigcup ^\infty _k_=_1 SPACE((logn)^k) $ (a) Show that, for any k, is $ A \in SPACE((logn)^k) $ and $ B \le _L A $, then $ B \in SPACE((logn)^k) $. (b) Show ...
0
votes
1answer
33 views

How can we show that $\lim_{n \to +\infty} f(n)=+\infty$?

We suppose that $\lim_{n \to +\infty} f(n)=+\infty$. I want to prove that if $f(n)=O(g(n)), c \in \mathbb{R}$, then $f(n)+c=O(g(n))$ . $f(n)=O(g(n))$ That means that $\exists c_1>0, n_2 \in ...
0
votes
2answers
38 views

Hardness of a special case of maximum matching

Input: A set of N Users $\{u_1, ..., u_N\}$. A set of M products $\{i_1, ..., i_M\}$. Every pair $(u,i)$ is associated with the probability of u purchasing the product i, $p_{u,i}$. Task: Assign ...
-1
votes
2answers
33 views

How may occupied positions are there?

Consider an array, that can have a huge ( or infinite ) number of positions, but only the first $n$ positions are occupied(only $n$ of them contain valid elements), and the remaining are empty. ...
1
vote
2answers
31 views

Bounds of Sparse Matrix Multiplication

Does anyone know a good reference for bounds on sparse matrix multiplication? I'm interested in bounds of the number of scalar products required and bounds of the sparsity of the product. I know that ...
0
votes
1answer
38 views

Big-Omega proof using L'Hopital's Rule?

Prove or disprove: $15n^2$ is in $\Omega(3 \times 2^n)$ So we'd have to prove or disprove this statement: $$ \exists c \in\mathbb{R}^+,\,\exists B\in\mathbb{N}, \forall n \in\mathbb{N}, n ≥ B ...
0
votes
1answer
18 views

Solving time complexity of merge sort

I was asked to prove that the time complexity of merge sort is $ O(log_2n)$ but I cannot find a way to continue my method. Any help? $T(n)=2T(\frac{n}{2} )+n$ $T(n)= 2[2T(\frac{n}{4})+n] +n = ...
-1
votes
1answer
15 views

Verification of $F(m)^{d} \pmod n \equiv m$ with very large inputs, where $F(m)=m^e$

Does anyone have the computational power to check whether or not $F(m)^{d} \pmod n \equiv m$, where the values of the variables are found below. According to Wolfram Alpha, I found the result of the ...
1
vote
2answers
25 views

Prove $8n^{3}$ $+$ $√n$ $∈$ $Θ$($n^{3})$

just wondering if I proved this question correctly. Any hints, help, or comments would be appreciated. There are two cases to consider to prove $8n^{3}$ $+$ $√n$ $ϵ$ $Θ(n^{3})$ $8n^{3}$ $+$ $√n$ ...
0
votes
1answer
42 views

Big Oh notation involving $\log n!\in O(n\log n)$

I have worked hard on these questions and have found my own approach. I'm just checking if it makes logical sense for others and works. I'd appreciate any hints or better approaches. Question 1: ...
1
vote
1answer
23 views

Algorithm to find string

Given a string $w$, we want to find the last string in the list, that precedes alphabetically $w$ and ends with the same letter as $w$. Example: $\text{ w=crabapple }$ $L=\langle \text{canary, cat, ...
1
vote
0answers
46 views

an instance of NP-complete

The cafeteria serves $m$ different kinds of food, $F = \{ f_i \}_{i = 1}^{m}$. The fruit are grouped into $n$ different types of bags $B_1, \cdots, B_n \subseteq F$. (The same kind of fruit might be ...
0
votes
0answers
44 views

Min cost flow problem for hypergraphs and multidimensional assignment problem

Multidimensional assignment problem is NP in general. There is an algorithm, which transforms the common assignment problem into min-cost flow problem. Why we can't do the same operation onto ...
1
vote
1answer
24 views

Prove that the subset sum problem with fixed size and number reusability is NP complete

I'm trying to solve the following problem: There are B (B is allowed to vary) lists of unspecified size containing integers. Pick a number from each list so that the sum of all the picks is exactly ...
0
votes
1answer
13 views

Multitape Turing machine with multiple non-blank tapes

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank. Are there any formulations of a Turing machine that allow other tapes to be not blank? ...
2
votes
1answer
312 views

what is the relationship between the complexity class E(and EXP) and NP?

I want to know any relationship between the complexity class E(and EXP) and NP. I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size ...
0
votes
1answer
18 views

Properties of carry in base $b$ multiplication

Consider $n$ bit numbers $A$ and $B$. Let they be represented in base $b$. When you multiply $A$ and $B$ using school multiplication: $(1)$ how many carry propagations can one expect? $(2)$ what ...