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
148 views

Calculate the time complexity for the following Travelling Salesman problem algorithm

Consider the following algorithm for solving the TSP: $n$ = number of cities $m$ = $n\times n$ matrix of distances between cities min = (infinity) ...
1
vote
0answers
30 views

Computational Complexity of the class of $\Delta_0$ functions (over $V_\omega$)

I would like to know where the class of functions whose graph is $\Delta_0$ (over $V_\omega$) fits in the computational complexity hierarchy. Also is there a nice notion of $\Delta_0$-reducibility ...
1
vote
0answers
37 views

is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
1
vote
0answers
69 views

Is discrete ultralogarithm harder than discrete logarithm?

Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing $g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ ...
1
vote
0answers
81 views

Expansion in powers

Let $n=2k, k \in Z_+$. Let $$P_k\left(\frac{t}{\sqrt n}\right)=n!\sum_{\begin{smallmatrix} n_1+\ldots+n_k=n \\ ...
1
vote
0answers
67 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
160 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
72 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
31 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
44 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
46 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
78 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
98 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
82 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
76 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
146 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
293 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
230 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
737 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
316 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
227 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
13 views

NDTM vs DTM running time of a program

I've found the following statement: If a program $P$ for Non Deterministic Turing Machine solves a decision problem in time limited by a polynomial $p(S)$, where $S$-size of input, then it can be run ...
0
votes
0answers
23 views

Let g and h be any functions from naturals to (0,infinity)

Let $g$ and $h$ be any functions $\mathbb{N} \to (0,\infty)$. Then $g(n) \in \Omega(h(n))$ implies there is some $N \in \mathbb{N}$ such that $g(n)\ge h(n)$ for all $n \ge N$. Picture of question : ...
0
votes
0answers
15 views

How to calculate recurrence $F(n) = F(n/u) + \Theta(n^k)$ where $u,k \in \mathbb{N}$

$\Theta$ is used as in Bachmann-Landau notation (often called as Big-O notation convention). How does one in general the recurrence relation of the following from: $$F(n) = F(n/u) + \Theta(n^k) ...
0
votes
0answers
10 views

(Un-)Decidability of the isomorphism/classification problem for complex manifolds

It is easy to find references for the undecidability of the question whether two (smooth) real manifolds are diffeomorphic and/or homotopy equivalent. One can even say that given a manifold $M$ it is ...
0
votes
0answers
18 views

Is this variant of the Stable Roommate problem NP-hard?

I want to organize $2n$ people ${A, B, C, \dots}$ in pairs. Each people rates every other one with an integer number going from 0 to 10. The ratings may not be reciprocal (i.e., A may rate B a 10, and ...
0
votes
0answers
39 views

Conjectured optimal running time for integer factorization

While detecting prime numbers is computationally fast ($O(\log^3 n)$), the fastest known algorithms to split a composite number into its prime factor are very slow (RSA cryptography relies on this ...
0
votes
0answers
37 views

How to pronounce the complexity of an algorithm

I have a few questions regarding complexity: How do you name this complexity: $ f(M,D) = O(M^D) $. Is it f is exponential in D and what exactly in M, polynomial? Just to confirm $ f(M,D) = O(MD)$ is ...
0
votes
0answers
18 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
21 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
8 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
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
14 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
7 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
12 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
14 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
32 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
16 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
35 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
17 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
42 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
27 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?