Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

2
votes
2answers
225 views

Solving Summation Expressions

I would like to know how do you solve summation expressions in an easy way (from my understanding). I am computer science student analyzing for loops and finding it's time complexity. e.g Code: ...
1
vote
0answers
45 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
0
votes
1answer
187 views

Solving a recurrence relation with floors and comparing it with other complexity classes

The problem that I am struggling with is the recurrance relation $T(n) = \lfloor(T(n/2))\rfloor + \lfloor(log \space n)\rfloor$ Where $T(1) = 1$ I am supposed to answer true/false to each of the ...
3
votes
1answer
174 views

Using the definition of big-oh notation, show that for any $k,\gamma>1$, $n^k=O(\gamma^n)$.

This question had been on my midterm in a course I took last year: Prove that for any $k,\gamma>1$, $n^k=O(\gamma^n)$. Intuitively, this makes sense. Even the fastest exponential algorithm ...
0
votes
0answers
35 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
4
votes
4answers
321 views

Computing partition numbers

Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
0
votes
1answer
133 views

Subset sum problem performance and benchmark

Looking for information about this topic (P vs. NP / Subset sum problem) I found next sample problem http://www.cs.utsa.edu/~wagner/CS3343/ss/ss.html Above URL contains a set of 100 integer values ...
7
votes
1answer
119 views

complexity of matrix multiplication

For $n\times n$ dimensional matrices, it is known that calculating $\operatorname{tr}\{AB\}$ needs $n^2$ scalar multiplications. How many scalar multiplications are needed to calculate ...
2
votes
1answer
144 views

Why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $N \log N$?

As the title says, why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $O(N \log N)$? This is a famous open problem in ...
3
votes
1answer
88 views

If P=NP, then NP = coNP. Why is this so?

I read that if we assume that P = NP, then NP = coNP. I am unable to understand why this is so.
11
votes
1answer
261 views

Why is factorization of large number hard

Why factoring a number is difficult compared to finding out if it is prime (which can be done in polynomial time) ? I would think they might be of similar difficulty in terms of computational ...
2
votes
1answer
77 views

Unknown symbol '#' in set

I am reading a text on Complexity theory. There is a set whose notation I cannot understand: "Let $\sum$ = {0,1,#}" From the context, and given that the book is used computer science courses, it ...
3
votes
1answer
99 views

Showing that #SAT is NP-hard

I need some hints to solve the following problem. (from Complexity and cryptography by Talbot and Welsh, chapter 3, exercise 3.6) Let #SAT be the function, mapping Boolean formulae in CNF to ...
2
votes
0answers
174 views

Polynomial Time Root Extraction

Given a consistent system of polynomial equations: $A_1(x_1, x_2, x_3 ... x_n) = 0$ $A_2(x_1, x_2, x_3 ... x_n) = 0$ etc... $A_n(x_1, x_2, x_3 ... x_n) = 0$ If we let $d_1, d_2, d_3... d_n$ be the ...
2
votes
0answers
89 views

Finding a matching to connect subsets of vertices

I'm studying a graph problem which, strangely, has applications in bioinformatics. I'm not asking for a solution, but rather for advice as to whether something similar to what I do has been studied ...
0
votes
0answers
107 views

Mathematical reason for 2-player turn-based games

I've been reading Games, Puzzles, and Computation which analyzes games through game theory and complexity theory. The authors introduce something called "Constraint Logic" as a way of modeling games ...
2
votes
2answers
355 views

How to reduce 0-1 knapsack to knapsack-like problem with overflow?

Consider a knapsack-like problem where there is a set of items, and each item has a cost $c_i$ and value $v_i$. The goal is to find a subset $S$ that minimizes $\sum_{i\in S}c_{i}$ with the constraint ...
0
votes
1answer
40 views

Complexity of bounded 2-player game

I was reading about bounded 2-player games in chapter 6.1 of Games, Puzzles, and Computation. "Bounded" here means theres some finite resource of the game which imposes a limit on the number of player ...
0
votes
0answers
24 views

Vertex Set Optimization

I have the following problem: Min $c^Tx$ Subject to: $Ax = b$ $x >= 0 $ Where A is an M x N matrix: But rather a single solution I would like to know the first K best solutions where $1<= ...
0
votes
0answers
28 views

A computational complexity problem

Consider $n$ arbitrary (but fixed) unit-norm vectors $\mathbf{x}_1,\ldots,\mathbf{x}_n$ in, say, $\mathbb{R}^d$. Let $\beta>0$ be fixed. For $\mathbf{y}\in\mathbb{R}^d$, define the binary ...
0
votes
1answer
33 views

Converting Maximum TSP to Normal TSP

Consider the Travelling Salesman Problem: Given N cities connected by edges of varying weights. Given a city A what is the shortest path for visiting all the cities exactly once that returns back to ...
6
votes
3answers
269 views

Which is easier to work out: determinant or inverse?

Suppose $A\in M_n(R)$ be a $n\times n$ matrix over some ring $R$. Which of the following two tasks is easier? to work out $\det(A)$; to work out $A^{-1}$. More specifically, I want to know the ...
1
vote
1answer
290 views

Absolute value optimization

If you have an LP Maximize/Minimize: $c_1|x_1| + c_2|x_2| ... c_n|x_n|$ Subject to: $Ax = b$ Can this be solved in polynomial time with respect to the amount of data used to represent the ...
2
votes
1answer
98 views

How much slower is a Turing Machine if you only give it one end of the tape to work with?

Turing Machines start with the input string and tape head in the "middle" of a tape that extends infinitely in either direction. Suppose instead that the tape head starts at the "far left" of the ...
0
votes
2answers
75 views

How to work out the inverse matrix $A^{-1}$ ?

Suppose A is a matrix over some ring R (might be non-commutative). How to work out the inverse matrix $A^{-1}$?
7
votes
1answer
421 views

efficient summation of $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$

I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} A_{ij}A_{jk}A_{ki}$, where $A_{ij}$ is the a ...
2
votes
0answers
100 views

Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
1
vote
1answer
150 views

$\Sigma_k^\text{P}$−SAT definition is not clear to me

I don't understand if by saying there are $k$ alternating quantifiers on the variables $x_1$,$x_2$...$x_k$, It means we quantify ALL variables (there are only $k$ variables in the SAT formula) or just ...
1
vote
1answer
85 views

What sequences / algorithms does $O(N \log\log N)$ limit?

Considering the big-o-notation, there are a variety of algorithms that have the $O(N \log N)$ computational complexity; such algorithms are for example the merge sort, fast fourier transform, etc. ...
2
votes
0answers
108 views

Comparing two character tables

Suppose that you are given two finite groups, for example, via their Cayley tables. One can efficiently compute their character tables (efficiently = polynomial time in the order of the group), this ...
1
vote
1answer
30 views

Finding the complementary language of a given language

I'm trying to figure out what's the complementary language of: L = {w#w : w∈{a,b}*, |w| = k} I think it's the language of all the words w#w where |w|!=k. I think my answer is not correct. How ...
2
votes
1answer
97 views

What does noncomputable really mean?

I believe I understand the definition of a noncomputable problem from an introductory computer science class, but I don't understand what it really means. One of my hypothesis was that a ...
5
votes
0answers
67 views

Homomorphism for a fixed graph NP-complete?

Let $G$ be the following Graph: We want to decide whether for an input structure $\mathcal{S}$ there exists a homomorphism $S \to G$. We will call this problem $HOM_G$. The task at hand is to show ...
0
votes
0answers
173 views

Its just one point… How do I find it?

Okay so here is the deal... I have a CLOSED convex polyhedron $Ax \le b$ (where $x$ is in $R^n$) and it has i vertices denoted $V_i$ such that $V_i = (x_{i1}, x_{i2}, \ldots, x_{iN})$ where $0 \le ...
0
votes
0answers
94 views

How to find the nearest power product?

We call power products the integers of the form $x^m*y^n$ for $m$, $n$, $x$, $y \in \mathbb{N}$. Given a number $u \in \mathbb{N}$, find the closest power product. How does one solve this ...
2
votes
0answers
251 views

Pseudo inverse of matrix: SVD vs $A^{T}(A.A^{T})^{-1}$

For a C++ implementation I have to calculate Moore Penrose Inverse (AKA pseudo inverse) of non squared matrices. I was wondering ...
3
votes
2answers
92 views

COMPOSITE $\in$P if and only if PRIME $\in$ P

Let COMPOSITE be the following decision problem. COMPOSITE Input: an integer $n \geq 2$. Question: is n composite? Show that COMPOSITE $\in$P if and only if PRIME $\in$ P. I think ...
0
votes
1answer
71 views

Finding average-case time complexity

I have an integer array and some x integer number. I'm looping through this array and compare each element with x, if there exists the exact element, the algorithm ends. The best case is B(n) = 1, ...
0
votes
1answer
78 views

algorithm to determine complexity of algorithms?

Given a decision problem X, can there exist an algorithm A which, given any algorithm B which solves X in finitely many steps, determines whether B runs in polynomial time? If such an A exists, when ...
0
votes
1answer
253 views

Integer Linear Programming (ILP): NP-hard vs. NP-complete?

I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind. It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
1
vote
0answers
23 views

How did we arrive at this form of Markov's Inequality in this proof?

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a proposition on $\textbf{ZPP}$($ \textbf{ZPP} = \textbf{RP} \cap \textbf{coRP}$-proposition $4.13$), ...
1
vote
2answers
47 views

Problem understanding a proof

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there's this example: Choosing an integer $a \in_R \{0,\dots,n\}$ using random bits. We assume that we ...
0
votes
1answer
37 views

Clarification on some mathematics formula

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a theorem on $\textbf{BPP}$ where I don't understand a few steps of its proof, it's totally independent ...
1
vote
1answer
48 views

Some problems about the proof of a theorem

There's a theorem in my book (Complexity and cryptography by Talbot and Welsh, chapter 4) where I don't understand some parts of its proof: THEOREM: Suppose $f \in \mathbb Z[x_1,..., x_n]$ has ...
2
votes
1answer
41 views

“Certificate” in the context of computational complexity

I can't find any definition for the word either in the book I am reading or online. What exactly does certificate mean in the context of computational complexity? For instance: [...]The above ...
1
vote
1answer
60 views

Input size measurement according to polynomial presenation

There's a paragraph in my book (Complexity and cryptography by Talbot and Welsh, chapter 4) that I don't fully understand: Let $\mathbb Z[x_1,\dots,x_n]$ denote the set of polynomials in n ...
8
votes
1answer
177 views

Applications of computation on very large groups

I have been studying computational group theory and I am reading and trying to implement these algorithms. But what that is actually bothering me is, what is the practical advantage of computing all ...
0
votes
1answer
42 views

Complexity of Code Snippet Without Knowing A Function?

I have the code snippet: int const n = 300; int nArr[n]; for(int i = 0; i<n; i++) { if(i >x) copyPrevious(nArr,i); } I need to find the complexity ...
1
vote
0answers
138 views

Calculate the time complexity for the following Travelling Salesman problem algorithm

Consider the following algorithm for solving the TSP: $n$ = number of cities $m$ = $n\times n$ matrix of distances between cities min = (infinity) ...