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

How would you prove this Big Omega complexity?

We're given $f(n)=\frac{1}{5}n^2-30n-5$ and $g(n)=n^2$, and are asked to prove $f \in \Omega(g)$. The exercise was posted, but no solution is given (this is not an assignment question). So by ...
1
vote
0answers
30 views

why some people use the notation $a \leq O(n)$?

When describing the algorithm complexity denoted by $c$, some people use $c \leq O(n)$ instead of $c =O(n)$ to show complexity. I cannot understand why they should use $\leq $?
1
vote
0answers
29 views

When does $A,A\cap B, A\cup B\in S$ imply $B\in S$?

Let $S\subset 2^{\Sigma^*}$ be some family of formal languages over some alphabet $\Sigma$. Consider the the following statement: $A,A\cap B, A\cup B\in S$ implies $B\in S$ For which ...
1
vote
0answers
36 views

Is it better to compute $A^tA$ once and then $Ax$ several times or compute $y=Ax$ and then $A^ty$ every time?

So I have this algorithm which given a matrix $A$ it assigns $A=A^tA$ outside the loop and then on the algorithm loop it solves multiple instances of $Ax$ for different $x$s, (meaning that it's ...
1
vote
0answers
227 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 ...
1
vote
0answers
102 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 ...
1
vote
0answers
28 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 ...
1
vote
0answers
57 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 ...
1
vote
0answers
48 views

Kolmogorov complexity of a computer?

Warning: Vague, unclear question ahead. Proceed at your own risk. The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the ...
1
vote
0answers
66 views

Oracles for TQBF

I've seen this question somewhere and I've been thinking about it a lot but couldnt think of an answer. Say you have oracles A and B for the TQFB (True Quantified Boolean Formula) decision problem, ...
1
vote
0answers
50 views

Combinatorial search by testing sets with fixed number of elements

I am struggling to see the complexity of the following combinatorial search problem. Could anyone help me? Consider a set $I$ of $n$ items known to contain $d$ defectives or less. Assume $d < ...
1
vote
0answers
39 views

Order of magnitudes comparisons

I need your help with the following. I need to determine how to order (functions) the following : \begin{align} &f(x)=(x/2)^{(x/2)} \\ &g(x)=x! \end{align} Note: I got both of them are ...
1
vote
0answers
107 views

Big-O estimate (smallest order)

I'm trying to give a big-O estimate for each of these functions, where I want to use a simple function $g$ of smallest order. I have them all done I just wanted to someone to run through and check ...
1
vote
0answers
74 views

Constructing a “one-way function” of two variables (a.k.a “stop my friend from hacking my game”)

This might be more of a computer science question than a mathematics one; I thought I'd start here but perhaps people might want to point me to a better forum, if this isn't the right one. ...
1
vote
0answers
118 views

Efficient algorithm to find a minimum spanning set for a given vector.

A few days ago a colleague proposed the following problem. Let $W$ be a finite subset of a vector space $V$, and let $v\in\langle W\rangle$ (the linear span of $W$). Is there an efficient ...
1
vote
0answers
53 views

Is finding a matrix out of some set with a given determinant a hard problem?

Given $n\ge 2\ \ ,\ u,v,k\ $ integers. Decision problem : Does a $n\times n$ - matrix with entries from $u$ to $v$ with determinant $k$ exist? In which complexity class is this problem ? Is it ...
1
vote
0answers
64 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
1
vote
0answers
78 views

GCD of high order polynomials(modulo large prime)

I want to solve the following question: Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...
1
vote
0answers
160 views

Find a simple Theta bound for a geometric series

I'm working on a question like: find a simple g(n) (big theta) for $ f(n) = \sum _{i=1}^n 5^i $ My working starts with this $\frac{5-5^n}{1-5}$ which is not equivalent to the correct answer from ...
1
vote
0answers
693 views

Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
1
vote
0answers
40 views

Is there a fast algorithm for computing the $(2^n)+1$ th last digit of $3^{2^n}$ in base $2$?

Is there an algorithm such that for some polynomial p, it always computes the $(2^n)+1$ th last digit of $3^{2^n}$ in base $2$ in at most p(n) steps for all nonnegative integers n? I'm only asking if ...
1
vote
0answers
35 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
1
vote
0answers
127 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
29 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
55 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
59 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
34 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
81 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
119 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
39 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
275 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
96 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
134 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
21 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
70 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
107 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
995 views

Exact inversion of matrix complexity (by Gaussian elimination)

I would like to check if what I have done is correct. Please, any input is appreciated. Problem statement: Consider a non-singular matrix $A_{nxn}$. Construct an algorithm using Gaussian elimination ...
1
vote
0answers
59 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
142 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
57 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
75 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
76 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
60 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
40 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
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
240 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
34 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 ...