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

Game Tree Complexity of Open Face Chinese Poker

I'm interested in working out the game tree complexity of a $1$v$1$ game of standard Open Face Chinese Poker and seeing how it compares to Chess (which is $\sim 10^{120}$). For those unfamiliar with ...
0
votes
0answers
8 views

Runtime Complexity | Recursive calculation using Master's Theorem

So I've encountered a case where I have 2 recursive calls - rather than one. I do know how to solve for one recursive call, but in this case I'm not sure whether I'm right or wrong. I have the ...
2
votes
1answer
19 views

Proving a language $L$ is in $\mathrm{co\text{-}NP}$ if $| L \cap \{0,1\}^n | \in \operatorname{poly}(n)$ for all $n$

Let $L \in NP$ such that $|L \cap \{0,1\}^n|=\operatorname{poly}(n)$ for all $n$. Prove that $L \in \mathrm{co\text{-}NP}$. If I understand the problem correctly, in words this says that "for any ...
0
votes
0answers
10 views

Coppersmith-Winograd algorithm

I'm interested in algorithms to compute matrix multiplications. Is the Coppersmith-Winograd algorithm similar to the Strassen algorithm ? I have two other questions: 1) Are the multiplications done ...
0
votes
0answers
22 views

How to approximate a trigonometric to make less computation complexity

I having a trigonometric function such as $$ p_2(s) = \begin{cases} \frac {1}{(2 \pi)^2}(1-\cos (2 \pi s)), & \text{if $s \le1$ } \\ \frac {1}{2 }(s-1)^2, & \text{if $s >1$ } ...
1
vote
1answer
26 views

Approximation of combination $ {n \choose k} = \Theta \left( n^k \right) $?

Is it a valid to say $$ {n \choose k} = \Theta \left( n^k \right) $$ for any $n$ and $k$? If so, how to prove it? Note: $k$ is not a function of $n$. Note: Observed it here (page 5): ...
0
votes
1answer
24 views

Why is $O(n^{km}+n^m)=O(n^{km})$?

I've seen this equation in one of my handouts $O(n^{km}+n^m)=O(n^{km})$, which doesn't seem obvious to me. This is what I got trying to work it out: $$\begin{align*}n^{km}+n^m &\leq C \cdot ...
0
votes
0answers
12 views

Recommended gentle introductory reading for computational complexity

I recently read this paper by Scott Aaronson titled: 'Why Philosophers Should Care About Computational Complexity'. I came across it via a link in Hacker News As somebody with a general interest in ...
1
vote
2answers
32 views

Is showing a graph is non-Hamiltonian NP-Complete?

Show that graph is not Hamiltonian. Is this an NP-complete problem? My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle ...
0
votes
0answers
10 views

Arithmetic circuit and complexity

Why scalar multiplications and additions can be considered free when looking at arithmetic circuits ? Thank you.
-1
votes
0answers
10 views

Fully Space Constructible Function [on hold]

Suppose S(n) ≥ n and S(n) is space constructible. Then show that S(n) is fully space constructible. Please help! :)
3
votes
2answers
69 views

An easy question about NP-hard

Consider an optimization problem includes two variables. If we fix the value of one variable, then the optimization problem over the other variable is NP-hard. Can it be concluded that the original ...
0
votes
0answers
30 views

What is an example of an NL-complete context free language? [on hold]

Setting Exactly as the title stated: please give an example of an NL-complete context free language? Current Solution Recall in the past we proved that $E_{DFA}$ is regular, so it is also context ...
1
vote
2answers
36 views

Quick solution check for the TSP

Given a solution for the Boolean satisfiability or the Hamilton cycle problem it's obvious whether it's true or not, but how does one quickly check whether a solution for the TSP (travelling salesman ...
0
votes
1answer
6 views

Given $L = L_1 \cap L_2$ where $L_1 \in NP$ and $L_2 \in coNP$, how do I express L as a symmetric difference of 2 sets in NP?

My ultimate goal is to show that $L \in PP$, but I need to figure out the title question first as an intermediary step. Any help is appreciated, thanks in advance.
3
votes
1answer
17 views

Computational Theory: Proof, Chomsky normal form

Prove or disprove: If $G$ is a CFG in Chomsky normal form, then for any string $w \in L(G)$ of length $n\geq 1$ then exactly $2n-1$ steps are required for any derivation of $w$. I'm stuck at where to ...
3
votes
0answers
49 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
0
votes
0answers
12 views

Depths of top-level multiplication algorithms

I've seen that the depth of the Cantor/Kaltofen algorithm is in $O(\log n)$. Are the operations for this complexity undifferentiated ? Or this complexity is in terms of multiplications only ?
0
votes
0answers
7 views

BFS Modification For Total Shortest Paths

I was given the following problem as an assignment but it is really confusing me: Consider the BFS algorithm. Given a digraph G = (V, E) and a starting vertex s ∈ V, this algorithm computes for ...
2
votes
2answers
60 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
1
vote
0answers
19 views

Coloring chordal graphs

It is well known that the graph coloring problem --- given a graph $G$ and a number $k\in\mathbb{N}$ decide whether $\chi(X)\le k$ --- is NP-complete. However, certain classes of graphs can be colored ...
0
votes
0answers
22 views

What are some techniques of specifying a molecules structure using the least amount of information?

For instance say I have a water molecule I can describe it's structure by two bond lengths and a bond angle. Are there any neat math tricks or representations of objects that I could use to describe ...
-3
votes
0answers
19 views

complexities combinaison [closed]

I have an algorithm, and I want to calculate its complexity. in fact it has two parts, the complexity of the first part is O(p) and the complexity of the second part is O(log(n)) , the ...
3
votes
1answer
52 views

Verifying whether a number is the determinant of a matrix

What is the (computationally) fastest way to determine whether a number is the determinant of a given real matrix? I am wondering if I have an upper bound on the absolute value of the determinant of ...
1
vote
0answers
18 views

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that $$c(\tau(a),\tau(1))+\sum_{i=1}^{a-1} c(\tau(i),\tau(i+1))\leq b $$ Prove ...
1
vote
0answers
37 views

Is there an optimal algorithm to calculate $2^n - 1$ in $\theta(n^n)$

The sequence $(f_{n})_{n \in \mathbb{N}}$ is defined by $f_{0} := 0, f_{1} := 1$ and $f_{n} := 3f_{n-1}-2f_{n-2}$ for $n \in \mathbb{N}_{0} \setminus \{0,1\}$. Is there an algorithm that takes an $n ...
2
votes
4answers
45 views

Two non-negative functions f,g such that $f \not\in O(g)$ and $ g \not\in O(f)$

Show that there exist two non-negative functions $f,g: \mathbb{N} \rightarrow \mathbb{R}$ such that $f \not\in O(g)$ and $ g \not\in O(f)$. It would be easy two find two such functions for which one ...
1
vote
1answer
37 views

Directly Obtaining the $n$th Value of a Lucas Sequence

(As an aside: This question lies relatively upon the border between the realms of Computer Science and Mathematics, and thus may be appropriate for StackOverflow as well.) I am in need of a method of ...
1
vote
0answers
51 views

the sum of the reciprocals of the primes

The sum of the reciprocals of the primes is $\sum \limits_{p}\frac{1}{p} \approx N \ln\ln(N)$ what about this sum where $p_{3}=3,p_{5}=5,p_{n}=\sum \limits^{N}_{j=5}\frac{1}{p_{j}} \sum ...
0
votes
0answers
11 views

Time complexity of a recursive function on a given set

I am computing a function $fun$ which is defined as follows. $fun(m,s)=\sum_{\sigma_{p}\subset s;|\sigma_p|=m}\left [\prod_{i}i\in \sigma_p \sum_{j=1}^{|s-\sigma_p|}\sum_{\gamma_p\subset ...
1
vote
1answer
25 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
1
vote
1answer
30 views

If $ f(n) = \sum_{i = 1}^{n} (n / i) \log(n / i) $ and $ g(n) = n ~ {\log^{2}}(n) $, then is $ O(f) = O(g) $?

I was trying to prove that if $$f(n) = \sum_{i=1}^{n}\frac{n}{i} \log\frac{n}{i} $$ $$g(n) = n \log^2n$$ then $O(f(n)) = O(g(n))$ I am not sure that it is the case, but based on my simulation ...
1
vote
0answers
51 views

Counting problem of combinations of symmetric matrix.

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below- $G$ is partitioned in to two sub ...
0
votes
2answers
37 views

P vs NP and Countable vs Uncountable Decision Space

I have noticed that whenever the scope of a problem is pushed to infinity, problems in NP have an uncountably infinite decision space whereas problems in P seem to have a countably infinite decision ...
0
votes
0answers
12 views

Find all groups that meets the condition

I have $n$ elements, each of them have two unsigned int attributes $x$ and $y$. Now I'd like to find out all the groups that fit the following condition: $A.x \geq B.y$ and $B.x \geq A.y$. The ...
0
votes
0answers
24 views

the asymptotic approximation of a sum

$p_{n}$ and $p_{j}$ are two primes with $p_{n}<p_{j}$ where the $n$ and $j$ denotes the $n$th and the $j$th prime. I have this sum $$\sum \limits^{k=\frac{b-p^{2}_{n}p_{j}}{2p_{n}p_{j}} ...
0
votes
2answers
44 views

Formula to calculate password cracking time in years, taking into account Moore's law and known adversary guessing power [closed]

We know that the biggest human rights violators in human history are capable of one trillion password guesses per second as of approximately January 2013. Assume that the 1 trillion guesses per ...
0
votes
0answers
18 views

Approach for this Popular Algorithmic Problem

Given a matrix we have to select one value from each row so that the total value cost selected is minimum. Now the problem is we cannot select column "0" to "J" in "I"th row if we have selected ...
46
votes
4answers
3k views

Is “A New Kind of Science” a new kind of science?

A couple of years ago I was reading "New Kind of Science" (NKS) by S. Wolfram, and it presented lot of interesting ideas for a young Physics undergraduate. Now that I am studying Mathematics however, ...
0
votes
1answer
32 views

decidability of a given language

The language EGAL is $\{(A,B): A \text{ and } B \text{ are DFAs with } L(A) = L(B)\}$ How do I prove that such language is decidable by testing every word of $A$ and $B$ until a defined length ? i ...
2
votes
0answers
34 views

Why isn't NP=coNP? [duplicate]

My understanding is that if a problem is in NP, there is a nondeterministic polynomial-time Turing machine that decides it. That is to say, if an NP problem has a solution, the NP machine has a ...
-1
votes
0answers
54 views

Is there a formula for $\sum_{r=1}^x({n+r-1})Cr$? [duplicate]

I have an algorithm who is something like this : MOD = 1000003 ans = 0 while (r) : ans = (ans + nCrMod(n + r - 1, r, MOD))%MOD r-- print ans ...
0
votes
1answer
43 views

The meaning of 'worst case'

When giving bound on convergence rate, complexity and so on, people sometimes will specify it by 'worst case'. What is the meaning of 'worst case'?
0
votes
2answers
30 views

Exponential vs Polynomial running time

As per this article: http://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time we know that exponential is worse than polynomial in terms of running time. Is it safe to say that ...
-1
votes
0answers
34 views

3SAT complexity

If I develop an algorithm which runs in $8^kn$ runtime for 3SAT problem (at most 3 literals per clause of boolean satisfiability problem) where $k$ is the number of clauses and $n$ is the number of ...
2
votes
0answers
18 views

On the equidistant distribution of $n$ points on a sphere $S^2$ by algorithm and their “validity” measures by statistical methods

I have found an algorithm for distributing $n$ points $P_0, P_1, ..., P_n$ (approximately) equidstantly on a sphere where $$\varphi_i = \pi(\phi - 1)i \qquad \theta_i= \mathrm {asin} (2i/n - 1), ...
0
votes
0answers
12 views

Complexity of recurrence containing geometic series.

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
2answers
30 views

Complexity of recursive algorithm.

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...
0
votes
0answers
18 views

Question about Karp reduction

friends. I have a curiosity about Karp reduction. What we need to do for reduction from problem X to problem Y is that 1) Transformation from Instance of problem X to Instance of problem Y can be ...
0
votes
1answer
31 views

What is the number of words of length $h$ in a sequence of subsets of words?

Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given an integer $k$, and $S$ a finite subset of $L$ define recursively the following sequence of subsets of $L$: $$\begin{align} A_1 ...