8
votes
1answer
69 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
1
vote
1answer
21 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
2
votes
1answer
29 views

Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
1
vote
1answer
43 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
0
votes
0answers
10 views

Can this language be solved in PTIME?

I would like to know why we cannot prove that $P \subsetneq PSPACE$ by considering the following language for some particular Turing Machine $M$: $L_M:=$ {$w : M$ accepts or rejects $w$ without using ...
9
votes
2answers
169 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
0
votes
0answers
42 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
-1
votes
1answer
55 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
0answers
63 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
0
votes
0answers
46 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
0
votes
0answers
27 views

Using the pumping lemma to prove that a certain language is not regular

I've been trying to understand the pumping lemma since forever, I just don't know what it does, I have no clue what any of it does. My college professor sucks, he thinks writing a bunch of stuff on a ...
0
votes
1answer
21 views

Reduction between languages in P

I have a simple question about the class P: Is there exist a polynomial time reduction between every two languages A, B in P?
0
votes
0answers
92 views

Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
2
votes
1answer
89 views

Questions about a computer science field

I would like to have some information about the computer science field, " Algorithmic and Systems Analysis ". Is this a field of theoretical computer science? What subjects are related with this ...
1
vote
0answers
25 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
1
vote
1answer
26 views

Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$ Thanks!
0
votes
1answer
29 views

Why $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$?

I was told that the complexity of $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with ...
2
votes
1answer
21 views

Checking if a graph is bipartite is $O(n)$

It seems to me that checking if a graph is bipartite (or biclique) has deterministic time complexity $O(n)$, where $n=|V|^2$, since we clearly have to iterate over all the elements of the incidence ...
1
vote
1answer
101 views

Is NP countable?

Is NP countable? I am confused with this problem. I think it is not countable but I am not sure. Can someone prove whether it is countable? Please show your proof. Thank you for your time!
1
vote
1answer
73 views

Solving recurrence relation: f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3

f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3 I have attempted to solve it by letting n = 2k f(2k) = 3f(2k-1) - 2f(2k-2) Then set S(k) = f(2k) S(k) = 3*S(k-1) - 2*S(k-2) ...
1
vote
0answers
52 views

Proving context free language membership is $P$ complete with respect to log-space reductions

This is exercise from Introduction to Automata theory, Languages and Computation, by Hopcrof, Ullman (first edition). I found example of polynomial reduction to some problems in logic, or graph ...
0
votes
1answer
25 views

Efficiency LL and LR parsing

My question is, is an LL parser or an LR parser more efficient (in big-O terms) ? I don't mean in terms of coding the parser, but rather in the context of the runtime of the parser. Is there a ...
1
vote
1answer
45 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
0
votes
0answers
21 views

Show L1 is in P, given that L2 is in P and L1 <=p L2

Given L1 and L2 are languages over alphabet Z. Also given that L1 <=p (polynomial time computable) L2 and L2 in P. What is the best way to show that L1 is in P (through definitions of class P and ...
0
votes
2answers
14 views

Linear search average-case complexity?

I am trying to find the average case complexity of the linear search. I know the answer is O(n), but is this correct: The first element has probability $1/n$ and requires 1 comparison; the second ...
1
vote
2answers
58 views

I want to know an estimate of $a_{i, j}$

Let $$ a_{ij} = \begin{cases} -1, & \text{if $i = -1$ and $j = -1$} \\ 1, & \text{if $i = -1$ and $j \ne -1$} \\ 1, & \text{if $i \ne -1$ and $j = -1$} \\ a_{i-1, j-1} + ...
1
vote
3answers
27 views

How do you reckon Big-O analysis with infinite problem sets?

Let $f : X \to Y$ be a problem, for instance, $f: \Bbb{Z} \to $ a factor. Given input measure $n = |x|$, then our problem is $O(g)$ if there exists an algorithm running on a standard machine, and an ...
0
votes
0answers
45 views

My notes on $\Bbb{Z}/p\Bbb{Z}$-theoretic computational complexity

(Question at the very bottom) Def 1. Let $F = \Bbb{Z}_p$ be a finite field. Then an $F^k$-machine is a machine with $k$ input / output memory slots. All computations are done in the field $F$ and ...
0
votes
1answer
22 views

circuits complexity

I ran into this claim and I dont really understand why it is true ( and I need to use it for proving other things) Every function from $(0, 1)^n$ to $(0, 1)$ is computable by a $2^n10n$-sized ...
0
votes
1answer
57 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
2
votes
0answers
31 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
0
votes
0answers
36 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
2
votes
0answers
17 views

A confusion about RP class of problems

I have some notes which introduces the quantifier $\exists^+x$ and interprets it as "the overwhelming majority of $x$". Then, it defines RP (Randomized Polynomial) as: $$ L\in RP\Leftrightarrow ...
0
votes
0answers
14 views

What are the current lower bounds for $NTIME$ vs $DTIME$?

Trivially, we have $DTIME(f(n)) \subset NTIME(f(n))$. Is it known whether or not this inclusion is strict? Do we know if $DTIME(f^c(n)) \subset NTIME(f(n))$ for any $c$? Is there any $c$ for which ...
2
votes
3answers
45 views

Help making the distinction between polynomial and exponential time

I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = $\{\langle G,s,t \rangle | G$ is a directed ...
0
votes
1answer
92 views

If the union of two languages is NP-complete, is one of them NP-complete?

Question 1) If $A\cup B$ is NP-complete, and $A$ is NP, and $B$ is P, then is $A$ NP-complete? I don't think so but I am unsure. When I try to reduce $A\cup B$ to $A$, I fail because strings in $B$ ...
0
votes
1answer
41 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
0
votes
1answer
34 views

Natural Decision Problem not in PTIME

Are there any natural decision problems which are guaranteed not to be in $\mathsf{PTIME}$? Preferably natural graph problems like $\mathsf{CLIQUE}, \mathsf{VERTEXCOVER}$ etc. (However, they would be ...
0
votes
0answers
17 views

Reduction of halting problem

I can show that this reduction !H ≤ H where H is the general halting problem an !H is the complement of it. But what with H ≤ !H ...
4
votes
1answer
25 views

Is anything nontrivial known about quotients of complexity classes?

This question is just for fun and this is completely outside my area, so it's likely dumb; apologies in advance. By a "quotient" I mean the following: suppose you have two complexity classes, $A ...
0
votes
2answers
135 views

The result of O(f(n)) - O(f(n))

My question is in the field of the big-O-notation and complexity/asymptotic functions: Probably something that I'm missing, but I've couldn't find any well explained solution for the following: What ...
1
vote
3answers
334 views

Big O notation - Proving that a function is not O(n)

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$. I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$. Many ...
3
votes
3answers
144 views

Why are the hierarchy theorem proofs called diagonalization?

Proofs of the various hierarchy theorems in theoretical computer science (see e.g. http://www.cs.princeton.edu/theory/complexity/diagchap.pdf) are usually called diagonalization proofs. Why they are ...
1
vote
1answer
64 views

What's wrong with this argument for $NP \ne EXP$?

Let $\{M_i\}$ be any enumeration of all Turing machines in which each machine appears an infinite number of times. Consider the language $D = \{i \, | \, M_i(i) \text{ does not accept within ...
1
vote
1answer
36 views

Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
0
votes
3answers
40 views

Reference for problems without efficient algorithm (in polynomial time)

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have: -Boolean satisfiability ...
1
vote
0answers
53 views

Implications of NP=coNP for PSPACE

If NP = coNP, then the Polynomial Hierarchy collapses to its first level (NP). Intuitively, it seems to me that PSPACE should collapse down to NP as well. As a loose heuristic argument, take the ...
0
votes
1answer
34 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
5
votes
2answers
207 views

NP-complete: One proof to rule them all

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown: There is a polynomial verification for $C$ solution. Every problem in NP is reducible to $C$ - You can solve all the ...
1
vote
1answer
149 views

Time complexity of binary sum

What is the time complexity of binary sum, the sum of two binary numbers done like in elementary school? Say one number is F and his length is $s$ bits, and another number is H and his length is $t$. ...