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
10 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
6 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
53 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
17 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
20 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
18 views

complexities combinaison

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
51 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 ...
0
votes
0answers
32 views

What is the complexity of finding roots of quintic polynomial with integer coefficients with integer roots? [on hold]

Given a degree 5 polynomial with integer coefficients, its Galois group is generally unsolvable. But suppose that we restrict the solution space to the subspace of quintic polynomials with integer ...
1
vote
0answers
36 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
43 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
35 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
50 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
47 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
35 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
11 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
42 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
16 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 ...
45
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
42 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
29 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
25 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
16 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 ...
0
votes
1answer
42 views

Confusion on Big $O$

I am so confused on the intuitive idea behind Big $O$ notation. $f(x)=O(g(x))$ iff there is a constant $C>0$ such that for large $x, |f(x)|\leq C|g(x)|$ and I have seen that in many places that ...
0
votes
0answers
23 views

What's the conjectured optimal running time for an exponential function algorithm restricted to [0, 1]?

If such an algorithm were used, for each positive integer ''n'', what's the upper bound on the computation time for the ''n''th digit after the decimal place. The Schönhage–Strassen algorithm runs on ...
0
votes
2answers
35 views

Required bits to communicate a partial order?

Suppose that you have a ranking (i.e. a strict complete partial order) over $n$ different objects, so that the objects can be ordered as $a>b>\cdots>n$. You want to communicate the exact ...
0
votes
0answers
23 views

Number of operation to transform $(0,0,0)$ to $(a,b,c)$ with $2^h\leq a,b,c \leq 2^h-1$

Given a positive integer $h$, define: $$A_h=[2^h,2^{h}-1]\big \{2^h-1+\sum_{i\in A}2^i \Big/ A\subset[0,h-1]\big \}$$ (this is in terms of binary expressions: the set of all numbers having exactly $h$ ...
2
votes
1answer
25 views

Average case complexity for checking if list is sorted

Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is ...
1
vote
0answers
58 views

A question on GCT

In http://ramakrishnadas.cs.uchicago.edu/gctriemann.ps it is stated that there is an unknown non-standard riemann hypothesis. AFAIK riemann hypothesis in AG was shown using Etale cohomology by Artin, ...
0
votes
0answers
7 views

How to find a strictly increasing sequence of words $(t_i)_{0\leq i\leq n}$ of maximum length ?

Let $L=\{0,1\}^*$ be the set of all words consisting of $0$ or $1$, we define an order in $L$ by: $$\begin{align}\forall (x,y)\in L^2 && \big( x\leq y&&\Leftrightarrow y=x\text{ or ...
8
votes
0answers
170 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
0
votes
1answer
20 views

Prove that $ (lg\; lg\; n)^k=o(lg^\epsilon n)$ for all $0<k,\epsilon$

I am stuck at this problem for a long time: Prove that $ (lg\; lg\; n)^k=o(lg^\epsilon n)$ for all $0<k,\epsilon$ I tried to show that $\lim_{x\to\infty}\frac{ (lg\; lg\; x)^k}{lg^\epsilon ...
-2
votes
2answers
82 views

What is the algorithm to add 2 binary with boolean operations? [closed]

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
0
votes
2answers
53 views

what is the complexity of this type of algorithms (loop bounded)?

I have an algorithm which contains only the instructions of type: $X_i=X_j$ $X_i=X_i+1$ $\text{while }(X_i\le N)\text{ do }\{C\}$ where $C$ is another instruction $N$ is a global constant and ...
1
vote
1answer
45 views

Minimize the squared dot product of two specific vectors

Do you think there exists a efficient algorithm(non brute-force) for the following problem. I search the optimal solution for the following problem: Given a vector $u=(u_1, u_2,..., u_k)^T$ with ...
1
vote
0answers
17 views

Traversing multi-way tree, computational complexity

This is a computational challenge. I am looking for a clever simplification or heuristic. Imagine a multi-way tree. Each node has three child branches. Consider them to be decisions; do A, do B, do ...
0
votes
1answer
40 views

improved segmented sieve of erastothenes complexity

I improved the segmented sieve of erastothenes , my algorithm doesnt repeat the multiples of primes using the equation $p^{2}_{n}p_{j}+2p_{n}p_{j} \times c =N$ wich shows when at least two multiples ...
2
votes
0answers
32 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
1answer
57 views

an strange set $ \Xi_A =$ {$ n \in N | \exists k^2 \in A $ s.t $ k^2 \leq n$} is decidable ?, an Interview questions?

We are some student that had an Interview for M.sc Entrance Exam. This interview has two part and one multiple choice question. We see 1 strange question that some definition is so strange for us, we ...