# Tagged Questions

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.

214 views

### Can the isomorphic graph problem be solved in deterministic polynomial time?

Here is a recent homework problem of mine: Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. ...
38 views

### is Co-NP in PSPACE?

Is Co-NP in PSPACE? I think it should obviously be, but I just wanted to make sure. I can find that NP is in PSPACE in Internet, but not on Co-NP.
64 views

### O(1) access into an array-like data structure with numerical ranges for keys

Preface: It's been a long time since I've been in school, and my terminology is probably all wrong. Apologies... Summary: I have a data structure with probability ranges assigned to the elements, and ...
47 views

### Proof of APSPACE = EXP

I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book. Please give a semi-detailed proof of this. I have found a paper which has this proof(by ...
15 views

### Term for an approximation that becomes better as the problem grows

For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and ...
49 views

### Sorting array with two elements - in place and minimal number of comparisons, lower bound

Algorithm must be in place. I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ ...
189 views

### AND operator of many functions

Suppose we have a set of functions $f_i: \mathbb Z \rightarrow \{0,1\}, i=1, \dots,n$, with the following property: For each $i =1,\dots ,n$, there exists an $x\in \mathbb Z$ such that $f_i(x)=0$ ...
474 views

### Can we show that non-determinism adds no power, for some specific running time?

$NP = \cup_{k \in \mathbb{N}} NTIME(n^k)$ $P = \cup_{k \in \mathbb{N}} TIME(n^k)$ Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$? For how large of a $k$ can we show the above ...
50 views

### Running time of amstrong algorithm

I have a problem how to find best, worst, average case in armstrong number algorithm? Here the pseudo-code : ...
38 views

### Complexity of union-find with path-compression, without rank

Wikipedia says union by rank without path compression gives an amortized time complexity of $O(\log n)$, and that both union by rank and path compression gives an amortized time complexity of ...
14 views

### Evaluate run time and compare these algorithms [duplicate]

Algorithm A divides the problem into 5 sub-problems of half the size. Solving each sub-problem then combining the solutions in linear time. Algorithm B solves problems of size n by dividing them into ...
53 views

### State of the art time complexity for getting (tree) descendants by type/attribute

Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only ...
66 views

### Counting the solutions to a restricted 0-1 knapsack problem

Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ : Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms. Output: ...
49 views

### Calculating execution time for recursive algorithm [duplicate]

How would I calculate the execution time, T(n), for this algorithm? ...
90 views

### What is the time complexity of checking if a number is prime?

Could some one please explain how to get the time complexity of checking if a number is prime? Im really confused as to if its O(sqrt(n)) or O(n^2). I iterate from i=2 to sqrt(n) and continuously ...
19 views

### Time complexity of minimizing Boolean expression

Given any arbitrary boolean expression using AND, OR and NOT gates what is the time complexity of minimizing the expression such that minimum number of gates are used. The following Wikipedia article ...
42 views

### Efficient method to sort very large set of integer vectors by all coordinates simultaneously

I have a set $E$ which is the set of all possible $d$-tuples ($d$-dimensional vectors) of integers between $1$ and $n$. Typically $d=3$ and $n\approx1000$, but for the sake of making a small example, ...
28 views

### What are the definitions for “hard problem” and “easy problem”?

Take for example the following sentence: Computing a hash for a message is "easy"; retrieving the message from the hash is "hard". Intuitively, I can perfectly understand what's written there. ...
43 views

### Convex Hull in no particular order

The proof for the $\Omega(n\log n)$ lower bound for calculating the convex hull by using order-type predicates that I have come across uses the fact that if there was possible to calculate the convex ...
111 views

### Time complexity of Ackermann's Function

How would one go about classifying the time complexity of Ackermann's function, and can we say that all primitive-recursive functions are asymptotically bounded by the complexity of the Ackermann ...
31 views

### What are some results for non-trivial lower bounds for the time complexity of decision problems?

Typically decision problems are studied in complexity theory and function problems are studied in the Analysis of Algorithms. Unfortunately, Complexity Theory tends to abstract over the exact time ...
97 views

### Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time?

My question may actually be more broadly described as: can I use the fact that an algorithm is expected to return $(O(f(n))$ answers to show that it may never run better than $O(f(n))$? I would ...
53 views

### Prove or disprove that $NL$ is closed under polynomial many-one reductions

If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$. Prove that the above claim is correct, incorrect, or equivalent to an open ...
23 views

### How to calculate runtime for FOR and WHILE loops? [duplicate]

While there have been many questions/answers around this on stackoverflow and wikipedia, I would like to have a clearer understanding on how to calculate it in layman's terms. I will say that, yes, ...
147 views

### Minimum edge deletion partitioning

I'm interested in the time complexity of the following problem: Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the ...
676 views

### Why do we say that polynomial time is easy? [duplicate]

For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so. ...
14 views

### Use of Landau notation for determining bounds [duplicate]

Assume that we have $l \leq \frac{u}{v}$ and assume that $u=O(x^2)$ and $v=\Omega(x)$. Can we say that $l=O(x)$? Thank you.
21 views

### Why worst case running time of Insertion sort is $\Theta(n^2)$ [duplicate]

From Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Theorem 3.1 For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if ...
69 views

### Is HORN-SAT in LIN, if so why is that not an indication that P=LIN?

The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time. $$LIN \subseteq P$$ Since HORN-SAT is solvable in $O(n)$ (as ...
58 views

### Devising an Algorithm for Linear Combination with Column Restrictions

Application: We intend to factor an integer $N$ using a variation of the rational sieve. This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ ...
114 views

### What is the best complexity of finding a minimum in a matrix?

Given a matrix $\mathsf{a}$ of size $K\times N$, what is the best complexity of finding the minimum value? Here is a pseudo code: ...
48 views

### Existence of randomized reduction but no deterministic reduction

What is the consequence to complexity theory of having a randomized reduction from an NP-complete problem to problem $\Pi$ while there is no deterministic reduction from an NP-complete problem to ...
61 views

### Is there a computation that takes the same amount of time to run on any computer? [closed]

I'm looking for research that has been done towards finding types of computations that take the same exact amount of time to run, regardless the amount of computing power one has. I've been thinking ...
51 views

### Merging of two convex polygon chains in O(log n)

Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the ...
96 views

### minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
116 views

### How to compare the time-complexity of an optimized algorithm with that of the original?

I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$). I managed to reduce the ...