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
0answers
66 views

Asymptotic notation of the following function

I have two functions, $f(n)$ and $g(n)$, and I am trying to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$. I am not sure about my answers. Help will be appreciated. a) ...
1
vote
0answers
154 views

Permutation Strategy for Sudoku solver NP-complete?

We know that Sudoku itself is $\mathbf{\mathsf{NP}}$-complete, but while trying to implement the "Permutation Rule" strategy in my solver, I was unable to find an efficient algorithm to do so. The ...
1
vote
0answers
70 views

Confusion related to time complexity of fast Fourier transform

I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT. It says that lets say I have a polynomial of ...
1
vote
0answers
52 views

Complexity of products/quotients of sums of roots of unity

This question was inspired by another recent question (here) . That older question asked somehow vaguely if the expression $\prod_{k=1}^m \tan(\frac{k\pi}{4m})$ can be simplified (for $m=45$). I ...
1
vote
0answers
30 views

Evaluating a simple sum bound

I'm trying to evaluate and prove a simple statement but It seems really raw/bad solution. I would like to advise with you if this is the right way because It is really getting more complicated than It ...
1
vote
0answers
43 views

SAT instance with exponential number of solutions

Given a SAT instance. If one knows that there are exponentially many solutions to that SAT instance, then can one find even one solution in polynomial time?
1
vote
0answers
45 views

$f(n) = n^2 \lceil \log n \rceil$ is time constructible

I have a question, I want to show, that: $$f(n) = n^2 \lceil \log n \rceil $$ is time-constructible. I have no idea how to do this. I know that $n^2$ is time-constructible and I know that $\log n$ ...
1
vote
0answers
76 views

Maximum Independent Set on Path and Ring

I known this question is more appropriate to cs.stackexchange.com, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic ...
1
vote
0answers
97 views

2sat approximation related problem.

Let $ { L }_{ \varepsilon }$ to be the language of all 2CNF formulas $\varphi $, such that at least $(\frac { 1 }{ 2 } + \varepsilon )$ of $\varphi$ 's clauses can be satisfied. Prove that there ...
1
vote
0answers
81 views

“Balancing” two infinities

Given these two computational complexities of 2 algorithms: $\exp(O(\sqrt{\log n \log \log n}))$ $O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$ where I imagine the first one goes to infinity slower ...
1
vote
0answers
74 views

Big Omega Proof Switch

Big omega definition: $f(x)=\Omega(g(x))$ if $f(x) \ge c g(x)$ Is it correct to switch it around to proof: $$g(x) \le c f(x)$$ I am afraid that moving the '$c$' to the other side may change the ...
1
vote
0answers
16 views

On the computational complexity of plugging in numbers into general expressions to obtain special ones

There are many expressions, which can be considered straight generalizations of others. I'm motivated by values of integral expressions specifically, for example there is $$\int_0^\infty e^{-a ...
1
vote
0answers
145 views

Does there exist a group (finitely presented) such that the isomorphism problem for the group and the trivial group is undecidable?

It is well known that the isomorphism problem for finitely presented groups is unsolvable. That is to say that if $G$ and $G'$are both fp- groups, then in general it is impossible to provide an ...
1
vote
0answers
51 views

existence of $DLOGTIME$-complete problems

Just curious - is there any problem that can be considered as $DLOGTIME$-complete? Or if not, has it been proven that there does not exist a complete class? (By being complete, I mean that it has ...
1
vote
0answers
287 views

Polynomial-Time reduction: Clique Problem

Here is an exercise my friend proposed to me: Show that the maximum clique problem polynomial time reduces to the maximum independent set problem. Here is my attempt at solving it: It is known ...
1
vote
0answers
213 views

Complexity of finding solutions for a system of polynomial equations

Problem A: Given a set of polynomial equations $ f_1=0,\ldots,f_m=0 $, where the $ f_i $'s are multivariate polynomials with $ n $ variables over a field $\mathbb F$, decide whether there is a ...
1
vote
0answers
732 views

Amortized analysis using potential function [Exercise from *Introduction to Algorithms*]

I need some help with the following problem from Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein: Consider an ordinary binary min-heap data structure with $n$ elements that supports ...
1
vote
0answers
134 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
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 ...
1
vote
0answers
307 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 ...
1
vote
0answers
220 views

approximate solution for bin packing problem that minimizes sum of max values of bins

I am trying to approximate the following NP-hard problem, which is similar to bin packing, but does not have a linear objective function: minimize $\Sigma_{i=1, \ldots, W}$ max{$v_s$ | s $\in$ ...
0
votes
0answers
14 views

Matrix operation repeat matrix members

I am going to use C++ Armadillo library which handles matrices to generate matrix $B$ and $C$ from matrix $A$. $$ A=[M_0,M_1,\ldots,M_{n-1}]^T $$ $$ ...
0
votes
0answers
17 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 ...
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 ...
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 ...
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
0answers
11 views

Turing machine that modifies each cell that contains a certain input one time at most

If I have a single tape turing machine running on some input $x$, where it modifies each part of the tape with $x$ one time at most...would the TM be decidable? Any advice or guidance appreciated; ...
0
votes
0answers
13 views

About the complexity of Mersenne numbers

In this page: http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test#Proof_of_the_Lucas-Lehmer_test In the end of this page I read this paragraph: The Lucas-Lehmer test, when used with the Fast ...
0
votes
0answers
6 views

solving and predicting complexity of a statistical model

How difficult/time consuming would it be for a professional mathematician to model a temporal probability distribution of when an event will occur when the temporal history of that event occurring is ...
0
votes
0answers
11 views

Amortized analysis: Understanding the potential formula

The potential formula is: $$\overset{\wedge}{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})$$ $\overset{\wedge}{c_i}$ the amortized time of operation $i$ is the actual time $c_i$ plus the change of the ...
0
votes
0answers
10 views

Asymptotics and function composition

In the following question: Big O and function composition It is explained that if $a, b, c, d$ are functions and $a = O(c), b = O(d)$ it doesn't mean that $a ∘ b = O(c∘d)$. However, what if we allow ...
0
votes
0answers
27 views

Simplify iterative logarithm

This is a homework question for my algorithms class and I have no clue how to start simplifying this function. I know log* is the iterative log function. It will equal the number of times you have to ...
0
votes
0answers
31 views

Are there problems known to be not in $P$ but not known to be outside $NP$?

Although most experts believe that $NP$ is not equal to $P$, for a long time I believed that of the two directions of attacking the $P$ vs $NP$ problem trying to prove that $P = NP$ is the more fun ...
0
votes
0answers
13 views

Computational Complexity, graph colourable question

K-colourability is the problem of deciding, given a graph G=(V,E), whether there is a colouring X={1,2,...,k} of the vertices by k colours 1,2,...k, so that no two vertices that are joined by an edge ...
0
votes
0answers
34 views

How to prove that $f(n)=O(g(n))$ without using the definition of big oh?

I have to indicate for $f(n)=\log n$ and $g(n)=\sqrt[k]{n}$ if $f(n)=O(g(n))$ and if $g(n)=O(f(n))$. For $f(n)=O(g(n))$: I found it hard to prove it using the definition of big oh so I decided to ...
0
votes
0answers
16 views

Big Oh proof. Need help finding c constant

Ok I have the equation . I have compared each term with 2^n and proved that 2^n is greater for some n_0. My problem is how do I gather the terms up and find the c? $ \sqrt[]{2}^{\log n} + \log^2 n + ...
0
votes
0answers
28 views

Gauss Jordan vs Gaussian Elimination and Back Substitution Efficiency

I have an assignment that claims that Gauss-Jordan Elimination has the same efficiency Gaussian Elimination with back substitution. I get this part; but the assignment asks me to show that from a ...
0
votes
0answers
26 views

Hardest case in checking for hamiltonicity?

The problem of checking if a given graph has a hamilton-cycle, is NP-complete. However, in practice, the known algorithm work well. I wonder if sparse graphs (only a few edges) are more difficult ...
0
votes
0answers
36 views

Prove or Disprove Asymptotic Complexity

Not sure how to prove or disprove this. $$\min\{f(n), g(n)\} \in \Theta\left(\frac{f(n)g(n)}{f(n)+g(n)}\right)$$ Could someone please give me a hint on how to approach this?
0
votes
0answers
33 views

Find two element $x_k$ and $x_l$

Let $S=\{ x_1, x_2, \dots, x_n \}$ a set of real numbers, where $n \geq 2$. Describe an algorithm, that has time complexity $o(n^2)$ and that finds and returns two elements $x_k$ and $x_l$ of $S$, ...
0
votes
0answers
11 views

Lowest complexity matrix multiplication using parallelization

I'm not very familiar with complexity calculations (though I'm trying to learn), but what is the fastest published way to multiply two square matrices together with a GPU? The estimate I can come up ...
0
votes
0answers
18 views

Problem in complexity class $P$ with highest known degree of a polynomial

Can someone help me find source where is listed complexity of most problems in complexity class $P$, particulary, I would like to know the one with the highest degree found so far. Somewhere I found ...
0
votes
0answers
31 views

Find the running time of the following program fragment

The exercise in my book is asking me to calculate the running time of the following for loop: for (int i = 0; i < n; ++i) ++k; This instantly reminds me ...
0
votes
0answers
29 views

Decision problem concerning magic squares

What is the computational complexity of the following decision problem ? Given : A list of $n^2$ natural numbers (not necessarily distinct) Question : Is there a magic square containing the given ...
0
votes
0answers
24 views

Generalization of standard technique for proving that an undecidable language is unrecognizable

Suppose $L = \{P:P(x) \; outputs \; x^2 \;for\; all\; x\}$ Then $\bar L = \{P: P(x)\; does\; not\; output\; x^2 for\; all\; x \}$. By Rice's Theorem or by reduction from the Halting Problem, let's say ...
0
votes
0answers
15 views

Can this language be solved in PTIME?

I would like to know why we cannot prove that $P \subsetneq PSPACE$ by considering the following language for some particular Turing Machine $M$: $L_M:=$ {$w : M$ accepts or rejects $w$ without using ...
0
votes
0answers
37 views

Language of Specific Grammar

I ran into this exercise in Sipser's Note on Computation Theory. Consider the following grammar $G$: $$\begin{align} S &\to aSD \;|\; bB \\ D &\to dS \;|\; a \\ B &\to bB \;|\; ...
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 ...
0
votes
0answers
63 views

sorting young's tableau better than n^3

Young's tableau takes $O(n^3)$ to sort. By sorting I mean sort numbers in existing young's tableau. http://en.wikipedia.org/wiki/Young_tableau Simply it is a matrix sorted by rows and columns. ...
0
votes
0answers
76 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...