0
votes
1answer
47 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
61 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
39 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
32 views

L={(M,W) | M is a Turing Machine that stops on input W } is not R. E.

I've been thinking about how to show this but I'm stuck. on Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific ...
0
votes
0answers
26 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
18 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
50 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
87 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
25 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
19 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
99 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
64 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
51 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
24 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
43 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
20 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
12 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
21 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
56 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
30 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
32 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
13 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
44 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
88 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
33 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
24 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
134 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
281 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
140 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
34 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
52 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
202 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
125 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$. ...
1
vote
0answers
59 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
1
vote
1answer
46 views

Amortized analysis and the potential method

To my understanding to use the potential method to get the amortized cost of an operation the following conditions need to be satisfied: $\Phi (D_{0}) = 0$ $\Phi (D_{i}) \geq 0$ for all $i \geq 0$ ...
0
votes
1answer
67 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
2
votes
2answers
69 views

Prove that $6^{\sqrt n} = O({n \choose n/2})$

Prove that $6^{\sqrt n} = O({n \choose n/2})$ I was able to show that prove that $6^{\sqrt n} = O({n \choose n/2})$ with defining $ n=2k$ and $ a_k= \frac {k!^26^\sqrt k} {2k!} $ and then show ...
1
vote
1answer
53 views

prove\disprove - there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$

there are functions $f(n)$ and $g(n)$ such that $g(n) = o(1)$ and $f(n-g(n)) \neq \Theta((f(n))$ Thought about $f(n) = |sin(n)|,\ g(n)= \frac1n$ then $f(n-g(n))= |sin(n-\frac1n)|$ and then for any ...
2
votes
0answers
70 views

Number of orderings of subset sums

In short: In how many ways can all $2^n$ subset sums of $n$ real numbers $a_1,\ldots, a_n$ be ordered? I am not concerned about the case in which different subsets sum to the same number; you may ...