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
21 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
10 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
21 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
49 views

Complexity of given recurrence [on hold]

I need to find an upper bound for the function T defined by the following relations: $T(1) = 1$ $T(n) ≤ 34 · T(n/17) + 17n$ Answer need to be tight up to $O(1)$ factors. Please help to solve this ...
0
votes
2answers
30 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 ...
43
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
31 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
53 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
40 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
28 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
22 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
11 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
29 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
17 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
29 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
41 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
22 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
24 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
57 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
168 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
40 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
40 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
39 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
30 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
54 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 ...
0
votes
0answers
42 views

Can you decouple the Traveling Salesman Problem from the number of cities?

I am studying the euclidian version of the Travelling Sales Man problem: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits ...
0
votes
0answers
45 views

Best time complexity for calculating the next, unique graph.

Whats the best time complexity, for a known algorithm, that when called generates the next, unique, graph, in order of node count? For example, the first result being the only single node graph, I ...
0
votes
0answers
19 views

Trying to determine the relationship of m and n in a Casting Out m under base n

While exploring $\mathbb{Z/n}$ I stumbled upon this It explains that Casting Out Nines works because our common counting system is decimal and thus there exist a congruence relation as follows ...
1
vote
1answer
13 views

Reducing a problem X to an np-complete problem Y.

Say I have a problem X that I can reduce to an NP-complete problem Y. Can I assume that problem X is in NP? Can it not be in NP?
1
vote
0answers
28 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 ...
2
votes
2answers
78 views

P vs NP - examples of P and NP

I'm currently studying 'p versus np'. Can someone help me in showing an example of a mathematical p problem and np problem? A clear worked example would be much appreciated. Many thanks in advance.
1
vote
1answer
46 views

On average, as a function of n, how many print statements are executed by the following algorithm?

On average, as a function of n, how many print statements are executed by the following algorithm? ...
0
votes
1answer
61 views

Better time complexity.

I am new to complexity theory and want to know, Which one is better time complexity(faster) for an algorithm ? \begin{equation} \frac{n^{k+\log_2(n)}}{\log_2(n)2^{n}} \end{equation} or ...
4
votes
1answer
80 views

Computing the order of a group element

This is a partially computer theoretic question, but is probably closer to math. I remember finding a paper from 1980's or so that had a proof of the fact that finding the order of a group element is ...
1
vote
1answer
39 views

Clarification over what NP means

I'm reading an informal definition of the decision class NP with a specific example being the standard knapsack problem and a decision variant of this problem. The example they are using is a ...
0
votes
0answers
9 views

Implications of deterministic Polynomial Identity Testing

It is well-known that polynomial identity testing (PIT) has a polynomial time Monte-Carlo algorithm. At the same time, no efficient deterministic algorithm is known. I came across a paper of Kabanets ...
0
votes
1answer
41 views

Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ [closed]

Suppose A is a arbitrary subset of Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ with respect to $ n \in A \Longleftrightarrow n \in A_n $ and $A_n$ is finte, which of them is True? a) A and ...
5
votes
4answers
61 views

What is the number of full binary trees of height less than $h$

Given a integer $h$ What is $N(h)$ the number of full binary trees of height less than $h$? For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't ...
0
votes
0answers
29 views

Kirchoff's First Law (Algorithm Complexity)

I want a help in understanding the figure and the complexity of Kirchoff's First Law Kirchoff's First Law states that the number of incoming flows into a node must be equal to the number of outgoing ...
0
votes
0answers
19 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
0
votes
0answers
26 views

Proof the Restricted Case of CVP is P-complete

Show that the following Restricted Case of CVP is P-complete: Like CVP, except the input circuit satisfying the following conditions: All gates are placed int layers; the inputs of a gate come from ...