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

Proving context free language membership is $P$ complete with respect to log-space reductions

This is exercise from Introduction to Automata theory, Languages and Computation, by Hopcrof, Ullman (first edition). I found example of polynomial reduction to some problems in logic, or graph ...
1
vote
0answers
26 views

Basic questions about descriptive complexity

I'm trying to learn descriptive complexity, and I'm having trouble on a basic level wrapping my head around what it means for a logical formula to define a computational language. I've tried and ...
1
vote
0answers
52 views

My notes on $\Bbb{Z}/p\Bbb{Z}$-theoretic computational complexity

(Question at the very bottom) Def 1. Let $F = \Bbb{Z}_p$ be a finite field. Then an $F^k$-machine is a machine with $k$ input / output memory slots. All computations are done in the field $F$ and ...
1
vote
0answers
34 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...
1
vote
0answers
54 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
1
vote
0answers
33 views

any approximation for $\sum_{i_3=3}^{n-k+3}\sum_{i_4=i_3+1}^{n-k+4}\sum_{i_5=i_4+1}^{n-k+5}\cdots\sum_{i_k=i_{k-1}+1}^{n} 1, (n \gg k)$?

Is there any approximation for $$\sum\limits_{i_3=3}^{n-k+3}\sum\limits_{i_4=i_3+1}^{n-k+4}\sum\limits_{i_5=i_4+1}^{n-k+5}\cdots\sum\limits_{i_k=i_{k-1}+1}^{n} 1, \quad (n \gg k)$$ ? We know that ...
1
vote
0answers
69 views

number of multiplication steps required to solve Ax = b

If we can factorize $A$ in $LU$, We can solve $Ax = b$ in 2 steps: Solve $Lc = b$ for c Solve $Ux = c$ for x As per the Linear algebra book by Gilbert Strang, each step takes $n^2/2$ number of ...
1
vote
0answers
95 views

Is Quadratically Constrained Quadratic Program (QCQP) in NP?

The general version of QCQP is NP-hard, but is it also NP-complete? That means, is there a non-deterministic algorithm, which solves QCQP in polynomial time complexity? If the general version of QCQP ...
1
vote
0answers
37 views

Why every regular language is in $\text{TIME}(n)$?

How can I prove that every regular language $R$ has linear time complexity, i.e. every regular language satisfies $$R \in \text{TIME}(n)$$
1
vote
0answers
185 views

A question on the computational complexity of Boruvka's algorithm

One algorithm that finds a minimum spanning tree in a graph in which all weights are distinct is Boruvka's Algorithm (also known as Sollin's Algorithm). On the page you would see once you clicked ...
1
vote
0answers
91 views

How to prove the NP-hardness of this scheduling problem

Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations ...
1
vote
0answers
133 views

How to compute this recursion in linear time?

Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ ...
1
vote
0answers
20 views

The $k$-th term in the graded lexicographical order is recursive

I recently constructed a proof that a computable universal function exists for the class of polynomials of $n$-variables. To this end, I adopted the graded lexicographical monomial order. However, I ...
1
vote
0answers
64 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
1
vote
0answers
88 views

Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
1
vote
0answers
52 views

If P = NP can asymmetric key exchanges still exist?

One functions are easy to compute (ie polynomial time checking) but hard to reverse. if P = NP does that mean that asymmetric key exchanges will be reduced from polynomial computation time and ...
1
vote
0answers
131 views

Derive 3D point array from multiple 2D projections of same point array

Let's assume that we have an array of $n$ 3D points, we don't know their coordinates (thus we have $3n$ indeterminate scalar values). We also have $m$ 2D projections with known coordinates (thus we ...
1
vote
0answers
55 views

Definition of Complexity Classes

The definitions I've seen for 'complexity class' all seem to be variations on "the set of problems that can be solved by an abstract machine of type $M$ using $O(f(n))$ of resource $R$, where $n$ is ...
1
vote
0answers
71 views

Quadratic Diophantine Primality Testing

Define a 2-Quadratic Group Operation as the following: A 2nd degree polynomial of the form: $$a_1x_1 + a_2x_2 + a_3x_1^2 + a_4x_2^2 + a_5x_1x_2 $$ Define a primal 2-quadratic group number as an ...
1
vote
0answers
61 views

Systematic way of creating the complement of a regular grammar?

Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular ...
1
vote
0answers
52 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
1
vote
0answers
25 views

How did we arrive at this form of Markov's Inequality in this proof?

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a proposition on $\textbf{ZPP}$($ \textbf{ZPP} = \textbf{RP} \cap \textbf{coRP}$-proposition $4.13$), ...
1
vote
0answers
201 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
1k views

How to calculate an orthonormal basis for a matrix?

Are there any specific, easy to compute, algorithms to build an orthonormal basis for a matrix in which each column has length one?
1
vote
0answers
33 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
70 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
82 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
71 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
183 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
73 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
53 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
33 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
50 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
49 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
87 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
84 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
155 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
52 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
349 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
785 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
138 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
87 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
388 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
230 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

Time Complexity of algorithm

Suppose I have an output of roughly $n^k k \log_{10} n$ digits where $A$ has $n$ elements and we have to list $n^k$ tuples with $k$ components each. What would be the time complexity class of such a ...