# Tagged Questions

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
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 ...
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?
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 ...
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 ...
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?
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 ...
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 ...
25 views

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 ...
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 ...
24 views

34 views

### Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
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 ...
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 ...
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$ ...
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 ...
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$. ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...