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)

7
votes
2answers
248 views

Hamiltonian Weighted Graph and Decision Problems

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
1
vote
1answer
31 views

Theory of computation

For any language $A$, $B$ and $C$ such that $A\subseteq B \subseteq C$, if both $A$ and $C$ are decidable, then $B$ is decidable. True or False? How can I find this?
2
votes
1answer
31 views

Complexity class of conditional dependency resolution

I have a problem I am (considering) writing an algorithm for, but which I suspect to be NP-hard. However, I have not been able to prove that it is in fact NP-hard. The problem is stated as so: Given ...
3
votes
2answers
48 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
0
votes
1answer
56 views

How to evaluate growth of input size from n to 2n in this case?

This is the question I am currently working on What is the effect in time required to solve a problem when you double the size of the input from n to 2n, assuming that the number of milliseconds the ...
3
votes
1answer
35 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
0
votes
0answers
22 views

Shouldn't big oh definition be if and if only if, not just if? [duplicate]

This is from Discrete Mathematics and its Applications Shouldn't the if in that definition be an if and only if? Say we know that $n^2$ is in O($n^2$). Then from one side of the if and only if, we ...
0
votes
2answers
26 views

How to come up with an interval for this Big Oh Problem?

This is from Discrete Mathematics and its Applications I'am trying to use the interval method like what was shown in this example Here is my work so far: I noticed that when $x > 5$, $2^x > ...
0
votes
0answers
6 views

Factorization of sum and difference of factorized coprimes

If I have the prime factors of two coprimes $a$ and $b$, is it possible to find the prime factors of $a + b$ and $a - b$ faster than a full factorization?
0
votes
1answer
22 views

Construct a Turing Machine M' such that if M accepts a then M' accepts a and if M doesnot then M' does not halt

Give a TM $M$. Construct a Turing Machine $M'$ such that 1)if $M$ accepts $a$ then $M'$ accepts $a$ and 2)if $M$ does not accept then $M'$ does not halt. I am thinking about a 2-tape TM, with ...
30
votes
4answers
582 views

What is the *middle* digit of $3^{100000}$?

The decimal representation of $3^{100000}$ has $47713$ digits. What is the $23857^{th}$ digit - i.e. the one in the $10^{23856}$'s place? There are lots of questions on this site asking for the ...
3
votes
0answers
49 views

Category theory and complexity classes

Is there any interesting way to make the set of computational complexity classes into a category? Almost every interesting mathematical class of objects forms a category after all.
-5
votes
1answer
93 views

Some inference in Automaton and Decidable Problems [closed]

Anyone could correct me that the following inference is True: ( G is a Context Free Grammar) There is an algorithm that decides whether the complement of $L(G)$ (language generated by $G$) is empty ...
2
votes
1answer
39 views

Theory Of Computation - recognizable and decidable

How to prove that for any language $A$, if $A$ is recognizable and $A \leq_m A^\complement$, then $A$ is decidable. I know this theorem - A language is decidable iff both it and its complement are ...
0
votes
0answers
27 views

Computing a lower bound for the minimal componentwise distance of vertices of polyhedra

Let $A$ be a matrix in $\mathbb{R}^{m \times n}$ and let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a polytope. I want to compute a lower bound on the minimal componentwise distance of two ...
0
votes
1answer
43 views

Decision Problems and Poly Time

We have Two Decision Problem A and B. we know A is NP-Complete, but B can be solved in $O(n^2lg^4n)$, and we know $B \leq_pA $ (i.e each problem of B can be convert to a problem of A in Polynomial ...
1
vote
1answer
51 views

Asymptotic and 3-SAT problem in Algorithm Course

my TA says just one of the following is True, anyone could describe me some detail about following three lines? 1- if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then ...
0
votes
0answers
13 views

Design a non-polynomial time PAC algorithm that learns the class of all boolean circuits?

Setting. Suppose we relaxed the constraint that PAC learner uses polynomially evaluable hypothesis class $\mathcal{H}$. Instead let $\mathcal{H}$ be the class of all Turing machines (not neccessarily ...
0
votes
1answer
29 views

How may times should I colour a colour palette to have distinct colours?

Suppose that we have a colour palette, i.e., an array of n elements, which needs to be coloured by distinct numbers. We are only allowed to use 0 or 1 to colour every elements in each colouring step. ...
0
votes
0answers
8 views

Is it true that if concept class $\mathcal{C}$ is efficiently PAC learnable, then is there an $(\alpha,\beta)$-Occam algorithm for $\mathcal{C}$?

Setting Suppose if concept class $\mathcal{C}$ is efficiently PAC learnable, then is there an $(\alpha,\beta)$-Occam algorithm for $\mathcal{C}$ for $\alpha \ge 1$ and $\beta < 1$? Current ...
3
votes
1answer
50 views

Simple factorials

I've been doing some work with factorials and the normal way of calculating them is simply not working so well. When the numbers get really big, doing iterative multiplications is not viable and gets ...
0
votes
0answers
34 views

Best strategy for this archery-based probability game

This is with reference to the comments posted by @Trenin on my answer to this question. He says that since 2 players strategies depend on each other, we can't get the best strategy so easily. My ...
0
votes
1answer
30 views

How to give a big O estimate/visualize for these while loop?

This is from Discrete Mathematics and its applications I am currently working on problem 4. I was able to see that for problem 2, that one operation one will run n times for every n(meaning in ...
0
votes
1answer
23 views

Show the correctness: $\log^3( n)\in o(n^{0.5})$

show the correctness: $\log^3 (n)\in o(n^{0.5})$? I started from this way $$\log \log \log( n) = n^{0.5}$$ then I take $\log$ for two parties $$\log\log\log\log( n) = 0.5 \log( n)$$ ...
0
votes
0answers
41 views

How to show that $2^x$ is not in $O(x^2)$?

This is from Discrete Mathematics and its Applications I am working on 2e. I knew right off the bat from previous computer science courses that 2^x is not in O(x^2). I am having a difficult time ...
0
votes
0answers
28 views

Why can't this inequality hold true for all n > k?

This is from Discrete Mathematics and its Applications I am having trouble with why the "inequality n <= C cannot hold for all n with n >k". Is this reasoning for this that there is no largest ...
3
votes
3answers
44 views

Is there a clever shortcut to showing that this function is in O(N^2)?

This problem is from Discrete Mathematics and its Applications I am currently working on 2a. I am trying to apply an example the book gave earlier Is there some similar clever trick I can apply ...
0
votes
1answer
19 views

Fingerprinting and randomized algorithms

My question is regarding the notes pages 1-2 specifically http://www.cs.berkeley.edu/~sinclair/cs271/n3.pdf I understand everything up to the point near the top of the second page where it says ...
1
vote
1answer
17 views

Is there a typo in this runtime analysis of selection sort?

This is from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf, slide 6. The instructor is doing a runtime analysis of selection sort. Here is ...
0
votes
2answers
15 views

Finding $2m+1=2\alpha k+\alpha^2$ quickly

Given some positive integer $m$ I'm looking for all solutions $\alpha,k>0$ to $2m+1=2\alpha k+\alpha^2$ with $0<k^2<2m.$ Right now I'm finding these by looping over each of these possible $k$ ...
1
vote
3answers
23 views

Recurrence Relations Closed Form

So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$ $\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 ...
0
votes
1answer
16 views

Using limits to prove a function is in the order of another function

I have to prove the following theorem: I am not asking for the whole problem, but am stuck on the first part (Proving that output of c implies g(n) is in the order of f(n)). I know the following: ...
0
votes
1answer
29 views

Big Omega problem : is $n^2\in\Omega (2n^2)$?

Is $n^2\in\Omega (2n^2)$? If we find the limit we can see $\frac{1}{2}>0$, which means it is true, but I haven't learned the limit method. I need to figure out using this definition $\exists ...
0
votes
1answer
26 views

Need help figuring out $O(log$ $n)$ algorithm

Let's consider a strictly decreasing function $f : \mathbb{N} \rightarrow \mathbb{Z}$. That is, $f$ takes as input any natural number $(i ∈ N)$ and returns an integer such that for any $i$, $f(i) > ...
0
votes
0answers
23 views

Let g and h be any functions from naturals to (0,infinity)

Let $g$ and $h$ be any functions $\mathbb{N} \to (0,\infty)$. Then $g(n) \in \Omega(h(n))$ implies there is some $N \in \mathbb{N}$ such that $g(n)\ge h(n)$ for all $n \ge N$. Picture of question : ...
0
votes
0answers
15 views

How to calculate recurrence $F(n) = F(n/u) + \Theta(n^k)$ where $u,k \in \mathbb{N}$

$\Theta$ is used as in Bachmann-Landau notation (often called as Big-O notation convention). How does one in general the recurrence relation of the following from: $$F(n) = F(n/u) + \Theta(n^k) ...
2
votes
0answers
34 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
0
votes
1answer
34 views

Solving a summation where the inner summation is limited by the iterator of the two outer summations

I'm trying to solve the following summation (where C is some constant) but I'm stuck because of the inner most summation which is limited by $i\sqrt[2]{j}$ where i and j are the iterators of the outer ...
-1
votes
1answer
47 views

Number of submatrices of sum K

I have an array $A[]$ of N elements ($N<=1000$, $-1000<=A[i]<=1000$). We define a Matrix M such that $M[i,j]= A[i]*A[j]$. In the resulting matrix $M$, we have to count the number of ...
2
votes
0answers
40 views

Book or paper recommendation about “Rube Goldberg Mathematics” // e.g. Longest path problems

First: My question is not be very specific, since I lack a concrete overview, but my idea/thoughts in a nutshell: I would like to have a recommendation of a good book, paper or article about processes ...
1
vote
0answers
26 views

When does $A,A\cap B, A\cup B\in S$ imply $B\in S$?

Let $S\subset 2^{\Sigma^*}$ be some family of formal languages over some alphabet $\Sigma$. Consider the the following statement: $A,A\cap B, A\cup B\in S$ implies $B\in S$ For which ...
1
vote
1answer
37 views

Determining the coefficient of $x^n$ in $\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$

I looking for an algorithm to efficiently find the value$\mod p$ of the coefficient of $x^n$ in a generating function of this form: $$\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$$ where $p$ is some prime ...
1
vote
1answer
14 views

some notations in algorithm analysis

Assuming $k$ is a variable, 1.then someone claims that the algorithm complexity is super-linear or sub-linear in $k$, here what is the meaning by using super-linear or sub-linear? 2.also, if ...
3
votes
0answers
58 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...
2
votes
0answers
38 views

how to count possible planar bipartitions?

i want to find out what small fraction of a solution space a metaheuristic search is actually covering. this case comes down to the number of possible bipartitions for a non-bipartite, undirected ...
3
votes
1answer
79 views

Applications of computer science to mathematics

I have been introduced to algorithms, computability and computational complexity (as part of my minor in CS). What are some mathematical topics that I can tackle with the new perspectives I ...
0
votes
0answers
21 views

Is this variant of the Stable Roommate problem NP-hard?

I want to organize $2n$ people ${A, B, C, \dots}$ in pairs. Each people rates every other one with an integer number going from 0 to 10. The ratings may not be reciprocal (i.e., A may rate B a 10, and ...
0
votes
0answers
45 views

Conjectured optimal running time for integer factorization

While detecting prime numbers is computationally fast ($O(\log^3 n)$), the fastest known algorithms to split a composite number into its prime factor are very slow (RSA cryptography relies on this ...
0
votes
1answer
32 views

Complexity of polynomial simplification into standard form

I am curious to know if any given $n$-variable polynomial in $\mathbb{R}[\mathbf{x}]$, not in standard form, can be simplified by an algorithm in polynomial time. The polynomial is $$ p(\mathbf{x}) = ...
0
votes
1answer
43 views

Complexity of factoring integers by trial division

Ok, I have a real problem with understand the complexity of this algorithm: set k=n; while k!=1{ while True{ d=k/i; if type(d)=integer{ i is a factor; break; } } } So we go through the internal while ...