Tag: prove

How to prove NP-hardness from scratch?

I am working on a problem of whose complexity is unknown. By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use.

Finally, I have decided to go for the most primitive method — Turing Machines.

Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might’ve messed up with the terminology here).

So, assuming that there are no problems to perform an NP-hardness reduction, how does one prove that a problem is NP-hard? Are there any publications that does this?

How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki “This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n log n) time: it performs n insertions at O(log n) cost each.[a]” we can also know if we build the heap using other methods. the big O could be better. Where should we begin if we would like to prove that the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n)), which is same as Big-O?

How to prove that the language {ww^Rx | w, x ∈ Σ+} isn’t regular?

$ $ L = \{ ww^R x\ |\ w, x \in \Sigma^+ \}$ $

Where $ w^R$ is the reversal of $ w$ , $ \Sigma = {0,1}$ , and $ \Sigma^+$ denotes the set of all nonempty strings over Σ. I’m trying to show that L isn’t regular via fooling sets but I can’t think of a good fooling set for this particular problem. I’ve been staring at this problem for hours but all I’ve noticed is that the first two characters in the fooling set can’t be the same. Anyone have any ideas?

Prove which languages are Recursive

Consider the following languages.

L1={ ⟨M⟩ ∣ M takes at least 1000 steps on some input},

L2={ ⟨M⟩ ∣ M takes at least 1000 steps on all inputs} and

L3={ ⟨M⟩ ∣ M accepts ϵ}, (ϵ = Null String)

Where for each Turing machine M, ⟨M⟩ denotes a specific encoding of M. Which one of the following is TRUE?

A. L1 is recursive and L2,L3 are not recursive

B. L2 is recursive and L1,L3 are not recursive

C. L1,L2 are recursive and L3 is not recursive

D. L1,L2,L3 are recursive

how to prove correctness of this BFS algorithm?

I wrote the following algorithm based on BFS. The algorithm detects wether a given undirected connected graph contains a cycle , if it contains a cycle then prints it. I’m pretty sure that it works just fine, but I don’t really know how to prove its correctness properly. Here is the pseudo-code:

Let s be the root set parent[s]=s and parent[v]=null for all other v create queue q ; enqueue(s,q); cycle=false; while (!isEmpty(q) && !cycle) {  u=front(q);  for every edge (u,v) incident to u {  if (parent[v]!=null){   parent[v]=u;   enqueue(v);  }  else if (parent[u]!=v){    cycle=true;    keep the edge (u,v)  } dequeue(q); if (cycle){  print edge (u,v)  while (parent[u]!=parent[v])&& (parent[v]!=u)&&(parent[u]!=v){         print edge (u,parent[u]) and  edge (v,parent[v])          u=parent[u];         v=parent[v];     }     if (parent[u]==parent[v])         print edge (u,parent[u]) and edge (v,parent[v])      else         print edge (u,v)  } /**************************************************/ /**************************************************/

I’ve been working on the proof but i can’t get through it. First i want to prove that if G contains a cycle then the algorithm does detect it. My idea is the following: Let s be the root of the bfs. We know that G contains a cycle, so there is a node such that there are two different paths from s to such a node. Let u be the first node that satisfies this. Since that BFS visits all the nodes, and explores each edge once, and also marks as visited all nodes that were visited, it will reach a step in which it is about to visit the node u for the second time and then it finds the cycle.

Then I want to prove that in the afirmative case, the edges that it prints does forms a cycle, but i’m really stuck with this.

How to prove by contradiction that every nonempty hereditary language contains the empty string?

A language L is called hereditary if it has the following property:

For every nonempty string x in L, there is a character in x which can be deleted from x to give another string in L.

Prove by contradiction that every nonempty hereditary language contains the empty string.

Here’s my attempt:

To prove by contradiction, we assume that for every nonempty string x in L, there is no character in x which can be deleted from x to give another string in L.

This means that if a character in x is deleted an empty string is left. Since an empty string is also a string, every nonempty hereditary language contains the empty string.

I’m not exactly sure how to proof by contradiction. Can someone help review this?