the amount of time resources (number of atomic operations or machine steps) required to solve a problem or run an algorithm with respect to the input size.

learn more… | top users | synonyms

2
votes
1answer
16 views

Efficient lookup when key is made of multiple elements and elements can be empty

I am wanting to create a map where the key contains multiple elements and the elements can be empty/null. The empty values are treated as "anything". I want to lookup function to match when the stored ...
3
votes
2answers
62 views

Count number of ways to place ones in an $M \times M$ matrix so that every row and column has $k$ ones?

On math.stackexchange, someone asked how to count the number of ways to place $1$'s into a $10 \times 10$ matrix so that every row and column has $5$ $1$'s. Each element of the matrix must be either ...
2
votes
2answers
89 views

Has there been any more progress on P vs. PSPACE compared to P vs. NP?

I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown ...
2
votes
1answer
97 views

Why is TIME(n log (log n)) \ TIME(n) = ∅?

In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be ...
0
votes
0answers
43 views

Why is password-cracking not a “fools mate” for P!=NP? [closed]

A password can be verified in polytime. Any NP-Complete problem can be reduced to the problem of determining a hidden password of length n. The problem of determining a password of length n clearly ...
3
votes
2answers
267 views

How to determine if a black-box is polynomial or exponential

I have a problem which essentially reduces to this: You have a black-box function that accepts inputs of length $n$. You can measure the amount of time the function takes to return the answer, but ...
2
votes
2answers
46 views

Is summing over all possible $k$-combinations NP-hard?

Say we have a set of numbers $A=\{a_1, a_2, \dots, a_n\}$, and we wish to sum over all possible combinations of $k$ terms to compute $$ \sum_{\substack{C \subseteq \{1,2,\dots,n\} \\ |C|=k}} \prod_{c ...
5
votes
1answer
41 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their ...
2
votes
1answer
20 views

Complexity as it relates to verifiers of languages

So I've been thinking about verifiers and a possible relation between a language's class and it's verifier complexity. From the book, "NP is the class of languages that have polynomial time ...
2
votes
0answers
26 views

Lower-bounds of running-time for output sensitive Algorithms

Let me ask my general question using a specific example, namely range searching: Given a set of points in the plane and an axis parallel rectangle, report all points lying in the rectangle. If the ...
4
votes
2answers
163 views

Performance impact due to time required for shuffling in Quicksort

As a programmer with non CS background, I am learning algorithms. When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the ...
2
votes
1answer
24 views

Polynomial hierarchy intersection

While familiarizing myself with polynomial hierarchy, I have come across a problem of showing $NP^{\Sigma_{k}^{p} \cap \Pi_{k}^{p}} \subseteq \Sigma_{k}^{p}$. By looking at the proof for $NP^{SAT} ...
5
votes
4answers
245 views

Approximating NP-complete problems

Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it. Could we get around this by finding an algorithm which ...
0
votes
2answers
89 views

Why is this algorithm $O(n^3)?$

In a programming book that I'm currently reading it's stated that $$\sum\limits_{i=1}^{n}i^2$$ is $O(n^3)$. My understanding was that $i\times i$ is a primitive operation and the complexity would be ...
2
votes
1answer
29 views

What is the time/space complexity of $n!$? Can $n!$ has polynomial space complexity?

Given an integer $n$, calculate $n!=n\times(n-1)\times(n-2)\dotsc 3\times2\times1$. What is the best time and space complexity of calculating $n!$? P.S. I do not have any idea about this topic. I ...
2
votes
1answer
33 views

Polynomial Hierarchy — polynomial time TM

Consider, for example, the definition for $\Sigma_2^p$ complexity class. $$ x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1, $$ where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some ...
2
votes
0answers
42 views

Which programming language is used at the Large Hadron Collider? [closed]

First off I am new to computer science (first semester) and do not know anything about physics, so I am appologizing up front for this not very scientific question. I've been wondering how data is ...
2
votes
2answers
78 views

Given a sorted array $A$, how can it be efficiently determined whether $\exists i . A[i] = i$? [closed]

Given an array $A$ of integers in ascending order, how efficiently can it be decided whether there exists an integer $i$ such that $A[i] = i$? How would an optimal algorithm for this problem work?
4
votes
3answers
70 views

Can somebody explain Horner's method of evaluating polynomials and how does it reduce the time complexity to 2n operations?

I have been trying to understand the difference between normal polynomial evaluation and horner's method. usually it takes 3n-1 operations while horner's method reduces it to 2n operations. I tried a ...
3
votes
1answer
45 views

Assume that SAT ∈ PSIZE, does it imply that NP = coNP?

Assume that $\mathrm{SAT} \in \mathrm{PSIZE}$, does it imply that $\mathrm{NP} = \mathrm{coNP}$ ? I think that I've managed to show that if $\mathrm{SAT} \in \mathrm{PSIZE}$, then both $\mathrm{NP}$ ...
2
votes
0answers
11 views

Generalized Geography with repetitions [duplicate]

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to move ...
1
vote
1answer
58 views

Generalized Geography with repetitions

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to ...
5
votes
1answer
83 views

How to compare algorithms in class NC time complexity with other classes?

I know these relations : \begin{gather} \mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \dots \subseteq \mathrm{NC}^i \subseteq \dots \subseteq \mathrm{NC} \\ \mathrm{NC}^i \subseteq \mathrm{AC}^i ...
0
votes
0answers
35 views

Total world computational capacity [closed]

I'm looking for some statistics for the total number of operations possible by all the computers in all the world now. A capacity factor for this (i.e. what fraction of the potential operations are ...
-1
votes
1answer
36 views

What's the time complexity of this append method? [closed]

I made a method that appends a sequence to another sequence. So: (append [1,2,3] [4,5,6]) = [1,2,3,4,5,6] CODE In C# ...
2
votes
1answer
36 views

Proof of sum of powerset?

Is there already a worst case time complexity proof for the sum of all elements in a power set? I would assume, naively, you have to just add everything, which would run in about 2^n, where n is the ...
10
votes
1answer
141 views

Runtime bounds on algorithms of NP complete problems assuming P≠NP

Assume $P\neq NP$. What can we say about the runtime bounds of all NP-complete problems? i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal ...
0
votes
0answers
10 views

Show polynomial hierarchy levels closed under reduction [duplicate]

Most books assume that this is obvious, but I can't see how each $\Sigma_k=NP^{\Sigma_{k-1}}$ level in the polynomial hierarchy is closed under polynomial-time reductions. Is there something that I'm ...
0
votes
0answers
19 views

Time complexity by solving recurrence relation [duplicate]

I was working on recurrence relation and came across this example T(n) = 2T(n/2) + log(n) What will be the time complexity, ie, big O for this relation. Thanks for any help in advance.
0
votes
1answer
26 views

Single big BST vs multiple smaller BSTs? Which is faster for search?

Lets say that I am storing 10^9 keys in a single BST. Compared to having lets say having multiple BSTs of sizes 10^6 containing ...
0
votes
1answer
19 views

The number of executions of the count statement; how many?

How many times does the statement count in line 5 executes in terms of $n$? ...
1
vote
0answers
16 views

Impelementing a stack using a 2 queues, and a queue using 2 stacks [duplicate]

I have thought about it for a while, and I'm not really sure what is the best way to: 1.Implement a stack using 2 queues. 2.Implement a queue using 2 stacks. I have only though about ...
0
votes
0answers
54 views

Reduction from Steiner tree to minimum set cover

I am trying to teach myself complexity. I am trying to come up with a reduction from minimum set cover (given a set of items I, and a set S of subsets of I and an integer k, is there a subset S' of S ...
4
votes
1answer
108 views

Relation of Space and Time in Complexity?

I'm looking for some clarification on some concepts/facts I came across while studying for a class. I was reading the following wikipedia article. The below specific section and statement intrigued ...
2
votes
1answer
97 views

Why is determining the size of a maximum independent set or a clique in P?

I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to ...
2
votes
0answers
129 views

Difference between deterministic and nondeterministic universal turing machine

It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a ...
1
vote
1answer
61 views

Time complexity of 8-queen, by placeing one by one without attack

I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack. One approach to achieve goal state is to "add a queen to any ...
3
votes
1answer
37 views

Recurrence relation in 2 variables

When analyzing an algorithm, the following recurrence relation popped up: $T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$ where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$. By applying the Master Theorem ...
4
votes
2answers
174 views

Time complexity of base conversion

EDIT As requested, a single question Why can't arbitrary base conversion be done as fast as converting from base $b$ to base $b^k$ ? There is a big time complexity difference, so I am also ...
0
votes
0answers
6 views

Applying the master theorem? Recurrence relation [duplicate]

T(n)=1 T(n)={ 2T(n/2) +lgn A=2 B=2 F(n)=lgn So doing so f(n) is an element of big theta of (nlg^2^2 * log ^k n) for k >= 0. (2n * log^k n). I'm unsure if I'm headed in the right direction but ...
0
votes
0answers
18 views

Recurrence relation help? [duplicate]

$$t(n)=\begin{cases}n&\text{if }n=0,1,2,\text{ or }3\\t(n-1)+t(n-3)-t(n-4)&\text{otherwise.}\end{cases} $$ Express your answer as simply using the theta notation. I don't know where to go ...
0
votes
1answer
25 views

How to analyse the complexity of a problem with two or more size measures

Consider this example: a problem of dimension $n$ and $m$ ($m,n$: any given integers). has a search space of size $O(n^n * m^n)$. It is clear that this problem is exponential in $n$, whatsoever $m$ ...
2
votes
1answer
22 views

Restricting longest path with 2-coloring to paths of at most constant length

I am trying to create a polynomial time algorithm for a problem defined as follows: c-ZPath(cZP) $c$ is an integer constant $\geq 1$ Input: An undirected graph $G=(V,E)$. ...
3
votes
0answers
26 views

PTAS vs. exact-time sub-exponential algorithms

I have recently summarized several algorithms for the maximum disjoint set problem. This problem is NP-hard, but it has both PTAS and sub-exponential algorithms. These algorithms seem to me closely ...
0
votes
1answer
39 views

What's the difference between “polynomial time Turing-reducible” and “polynomial time many-to-one reducible”? [duplicate]

The following definitions are from Li, M., & Vitányi, P. (1997). An introduction to Kolmogorov complexity and its applications (2nd ed.), pg. 38. A language $A$ is called polynomial time ...
3
votes
1answer
84 views

Digraph problem relating in- and out-degrees

Given a digraph $D = (V, A)$ and $m \in \mathbb{N}$, the question is is there a subset $A' \subseteq A$, such that $\lvert A' \rvert \geq m$ and $d_{D'}^+(u) \leq d_{D'}^-(v)$ holds for every arc $(u, ...
5
votes
1answer
126 views

Largest set of vertices that is larger than its set of neighbors

I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\{1,...,n\}$. For every subset $X' \subseteq X$, they define ...
1
vote
0answers
115 views

Complexity to find cube root of n [closed]

The cube root of a natural number n is defined as the largest natural number m such that m^3≤n. The complexity of computing the cube root of n (n is represented in binary notation) is (A) O(n) but ...
1
vote
1answer
102 views

how to solve NFA acceptance problem in polynomial time

I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires ...
0
votes
0answers
76 views

Sieve of Eratosthenes vs. Sieve of Sundaram

Relevant Information: Sieve of Eratosthenes Sieve of Sundaram Suppose I want to generate all primes in [2,n], and I have both of these algorithms at my disposal to ...