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
1answer
27 views

Does storage scheme matter in multiplication of two matrices? [closed]

Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity ...
1
vote
1answer
30 views

Zero-One Optimization

I have looked through some resources with varying success. Perhaps someone can provide a place to start. Suppose we have a finite set of real numbers, $A$, and a partition, ...
0
votes
1answer
30 views

Complete trail - walk traversing each vertex at least once, each edge at most once

I would like to know the status of the following problem: Given a simple graph, is there a walk traversing each vertex at least once and each edge at most once? (I am asking for a complete trail, a ...
1
vote
1answer
29 views

Changing variable in summation

I'm trying to understand the analysis of Quick Select algorithm that I found on StackOverflow: http://stackoverflow.com/a/25796762/3356218 Case 1 of proof: I understand it but the first transition, ...
1
vote
1answer
11 views

Binary enconding length

What does binary-encoding length means? For instance if my theorem says "An algorithm solves in time which is polynomial in n and in the binary-encoding length $<l,u,b,w>$ of the rest of the ...
2
votes
0answers
9 views

Complexity notation (Omega) consequence

In my algorithms class, the professor told us that the following holds: $$ \text{If } f(n) = \Omega(\log_2 n) \implies 2^{f(n)} = \Omega(n)$$ But is this always true ? I couldn't come up with a ...
0
votes
1answer
19 views

What the proof, instance, and verifier mean in the definition of NP problem?

I came across a definition of NP problems: Definition. A decision problem $X ∈ NP$, if there exists a polynomial time verifier $V$ such that For every yes instance $x ∈ X$, there exists a ...
1
vote
0answers
36 views

Understanding AI through a complexity function

I've been trying to understand in light of a few apparent paradoxes for me. It appears reasonable that we could prove any mathematical problem that has a well defined answer can be solved by a ...
0
votes
0answers
12 views

Does 'polynomial' (or 'exponential') running time for 3-SAT problem refer to the number of variables or the number of clauses?

This sounds like an incredibly stupid question but none of the relevant Wikipedia pages seem to answer it. So... if the runtime of an algorithm to solve 3SAT has running time $O(f(n))$ for some ...
1
vote
0answers
18 views

Akra-Bazzi method - constructive proof

As I was familiarizing myself with different methods of computing complexities of recurrences, I stumbled upon the Akra-Bazzi method. Seeing such a beautiful result literally made my day. I was able ...
0
votes
1answer
45 views

equivalence of theory of reals and Rationals

Present a sentence φ that is in theory of reals but not in thoery of Rationals Following up from this question what is the approach to show that both the theories are equivalent Th(R, 0, 1, +, ≤) ...
-2
votes
1answer
54 views

P vs NP, finding algorithms in polynomial time?

Concerning an NP problem, such as the travelling salesmen problem. Say for a graph with N nodes there exists an algorithm $A(N)$ which can solve the problem in time $N^3$ (for example). But.... to ...
0
votes
1answer
43 views

Statistical distance and test

Here is a bit of context and definitions: Let $\mathcal D$ and $\mathcal E$ be distributions of probability over a finite set $A$ and $X, Y$ be random variables following $\mathcal D$ and ...
1
vote
1answer
35 views

How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $

I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ Can any body explain this to me in simple terms. Any help on this is highly appreciated.
1
vote
1answer
15 views

Convex hull from cloud of co-ordinates

I'm trying to design an algorithm to find the convex hull of a set of co-ordinates using the slope between two points to determine if a point is part of the convex hull. I'm testing a set of five ...
0
votes
0answers
19 views

Pspace Complete Problem

image1 image2 In theory of computation text book I was going through this problem ... I have added the images What I wanted to know is that in the middle of the problem it is given that "Using this ...
0
votes
1answer
26 views

Big O - Recurrence

I am given a function as follows: ...
0
votes
0answers
21 views

Complexity theory : Lower Bound for the Theory of Real Addition

In theory of computation text book I came across this page ... I have added the images I wanted to know what at the bottom of the page it is given that However,we can combine these into one ...
0
votes
0answers
111 views

Cover of vertices - NP Algorithm analysis, correctness and execution time

Introduction Given a graph $G = (V, E)$, we call a set $T \subseteq V$ a cover if any edge $e \in E$ has one extremity in T. Decision Problem: Given $G = (V, E)$ with n nodes and a $k \le n$, return ...
0
votes
0answers
9 views

lower bound Tutte polynomial for planar graphs

The Tutte Polynomial $T(G, x, y)$ s a #P-Hard problem except for the hyperbola (x-1)(y-1)=1 and some other specific points. For the case of planar graphs, Dell $\textit{et. al.}$ mention (in the ...
0
votes
1answer
110 views

How we decide for a given context free grammar generate an infinite number of strings?

Consider the following decision problems: (P1) Does a given finite state machine accept a given string? (P2) Does a given context free grammar generate an infinite number of strings? Which of the ...
0
votes
1answer
19 views

Getting big Oh from summation

Merging two sorted arrays $A_1$ and $A_2$ with $n_1$ and $n_2$ elements, respectively, takes $O(n_1+n_2)$ time. This strategy begins by merging two arrays of size $n$ to create an array of size ...
0
votes
1answer
17 views

Need help in understanding proof “approach” and meaning for “1st order Theory of dense linear orders w/o endpoints is PSPACE complete”

So in my class we are giving a proof for 1st order Theory of dense linear orders w/o endpoints is PSPACE complete. The proof that it is in PSPACE is basically to reduce TQBF. Let $\phi = \exists ...
1
vote
0answers
10 views

Comparing the orders of complexity.

I do have to evaluate a property defined as $$w = \sqrt{\det\left(\textbf{J}\,\textbf{J}^\text{T}\right)} = \prod_{i = 1}^n \sigma_i,$$ where $\textbf{J} \in R^{3 x n}$ and $n>3$. Using the ...
0
votes
0answers
39 views

Hilbert 10th, bounded arithmetic, NP=co-NP

I keep seeing claims that if Hilbert 10th, if can be proved in bounded arithmetic (specifically $T_{2}$), then it will automatically mean that NP=co-NP. Unfortunately, none of these claims provide any ...
1
vote
4answers
136 views

Newton form vs. Lagrange form for interpolating polynomials

I'm just wondering, what are the advantages of using either the Newton form of polynomial interpolation or the Lagrange form over the other? It seems to me, that the computational cost of the two are ...
0
votes
0answers
27 views

Size of input relate to numbers of operations. Is it exponential?

Let assume that size of input is: $$ O( \log b + \log n) $$ and amount of operations on input is: $$O(b\log^2n)$$ Is amount of operations exponential relate to size of input? My intuition is: yes ...
0
votes
1answer
28 views

time complexity [closed]

Given n integers a1,a2..an and some integer S. To test whether there exists xi belongs to {0,1} such that: ...
1
vote
5answers
61 views

What's “computer's method” in calculating beta for a regression line

Since this is not from a problem set but just something I've been thinking, please forgive me for possible (wording) errors. Consider a set of data points $(x_n,b_n)$. We would like to know the ...
0
votes
1answer
24 views

Hardest boolean formula circuit complexity upper bound

I have stumbled upon Shannon's result that states that the maximum number of gates in a circuit needed to compute a boolean function on n bits, $f:\{0,1\}^n \to \{0,1\}$, is $\Theta (2^n/n)$. So far ...
0
votes
0answers
38 views

Proof of NP-completeness in the strong sense

I am just learning about the $\textbf{NP}$-completeness in the strong sense. I know that the $3$-partition problem: A set $X$ of $3n$ positive integers and a positive integer $B$ is given where each ...
0
votes
2answers
25 views

Is the concatenation of two arbitrary alphabets is considered an alphabet?

Is the concatenation of two arbitrary alphabets is considered an alphabet ? Also Is the set of all Java reserved words is considered an alphabet ? I am inclined to say yes. We could take a string and ...
0
votes
1answer
68 views

Is $P=NP$ an $NP$-complete problem?

Is $P=NP$ an $NP$-complete problem? In other words, is it possible (and does it make any sense) to show that proving $P=NP$ (or $P\neq NP$) cannot be done in polynomial time? I am not even sure it ...
0
votes
0answers
16 views

Turing machine that accept L = {ww} in linearithmic time

I was wondering if there is a way to design a deterministic turing machine that accept the language L = {ww} with a time complexity of O(n log(n))
2
votes
1answer
30 views

How many times will the statement 5 be executed?

I tried to calculate that, and I found that it is $\log n (\log n +1)(2\log n+1)$ ...
0
votes
0answers
21 views

Finding biconnected components of bounded size

Let $G$ be a simple graph with $n$ vertices where every biconnected component of $G$ has at most $c$ vertices. Let $v_1$ and $v_2$ be two adjacent vertices in $G$; $v_1$ and $v_2$ identify a unique ...
0
votes
0answers
11 views

Asymptotic analysis of an algorithm, difference between theoretical model and actual implementation.

I was wandering how a computational analysis should be performed in the following situations: Theoretical model Software model Let me show you an example (formula 1) $$x^2 = \sum_{i=0}^{n - 1} ...
1
vote
1answer
51 views

Derive a ϴ(1) formula for a Recurrence relation

I'm given a piece wise function with sequence $a_0$ $a_1$ etc $$a_n = \begin{cases}8 & n=0\\-7 & n=1\\25 & n=2\\7a_{(n-2)}+6a_{n-3} & otherwise\end{cases}$$ I'm asked to derive a ...
0
votes
1answer
22 views

Calculate bigO notation of recursive relation

I am attempting to calculate the big O notation for a simple recurrence relation $$T(n) = T(n/2) + 1\quad\text{when}\enspace n ≥ 1$$ $$T(1) = 1$$ So my attempt was as follows $$T(n) \le ...
2
votes
1answer
125 views

Giving an asymptotically tight bound on sum $\sum_{k=1}^n (\log_2 k)^2$

I am trying to give an asymptotically tight bound for the sum $\displaystyle\sum_{k=1}^{n} (\text{lg}k)^{2}$, where lg denotes the base 2 logarithm. I really have no idea where to begin, and I've ...
20
votes
3answers
737 views

Complexity of computing $ABx$ depends on the order of multiplication

To calculate $y = ABx$ where $A$ and $B$ are two $N\times N$ matrices and $x$ is an vector in $N$-dimensional space. there are two methods. One is to first calculate $z=Bx$, and then $y = Az$. This ...
1
vote
1answer
93 views

Big O with multiple variables ($n,m$): Is $O((n+1)^m) = O(n^m)$?

In the big O notation with multiple variables ($n,m$), is $O((n+1)^m) = O(n^m)$? Details: My intuition said yes, since adding a constant should neither have an effect in big O notation, even in a ...
0
votes
1answer
18 views

Is this proof of the worst-case performance of linear search correct?

I am sorry for the triviality of this question, but is this proof of the worst-case complexity of linear search correct? Claim. Let $L$ be a list of length $n$ and $k$ a target value in $L$. Then in ...
0
votes
0answers
18 views

Ph has log complete set

how can I show that PH has a ≤log m -complete set if and only if it collapses I am CS major and I do not have much Idea on how to do mathematical proofs
0
votes
0answers
16 views

What's a good book that touches on computational complexity theory and combinatorics?

I'm taking a class in enumerative combinatorics. The professor focusses on the complexity of solving combinatorics problems like partitions etc. I'm using Enumerative Combinatorics but it does not ...
0
votes
1answer
33 views

P is properly contained in DTIME(T'(n)).

There is a function T (which is not time-constructible, but is computable), such that $ P = DTIME(T(n)) \, . $ For every polynomial $p(n)$ , it holds that $p(n)=o(T(n))$. For every ...
0
votes
1answer
80 views

Worst Case Analysis

For the following algorithm, the function base() is to be considered the basic operation. The size of the input is given by n. Perform a worst-case analysis: for(i = 0; i < n; i++) for(j = 0; ...
0
votes
0answers
9 views

What is the complexity of finding f-reducing polynomial?

For a finite field $\mathbb F_q$, where $q$ is a power of prime. I want to know that complexity of finding f-reducing polynomials. The following is a definition of "f-reducing polynomial" Def) If $h ...
0
votes
1answer
48 views

Master theorem for $T(n) = 9T(\frac{n}{3}) +4n^6$

based on master theorem, I arrived at $$n^{2} ,f(n)=4n^6$$. So is the answer $$\theta(4n^6)$$ or is it just $$\theta(n^6)$$. And also, can this be solved with substitution method?