Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [proof-techniques]

Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.

0
votes
0answers
38 views

Prove or Disprove: If A is regular and A ∪ B is not regular, then B is not regular

I'm doing a problem where I need to prove the following statement: If A is regular and A ∪ B is not regular, then B is not regular. In another similar problem that I did, I know that if A is regular ...
2
votes
1answer
38 views

Union of infinitely many regular languages [duplicate]

I need to prove or disprove the following statement. If $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular. I know that if two languages ...
0
votes
1answer
63 views

Proving the singleton language {x} is regular for all x ∈ Σ*

So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would ...
2
votes
2answers
52 views

Proving that Every Full Prefix-Free Language is Maximal

I'm practicing a problem where I need to prove that every full prefix-free language is maximal. I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, ...
0
votes
1answer
48 views

Proving that A(B ∩ C) ⊆ AB ∩ AC

A(B ∩ C) = { UV | U ∈ A, V ∈ B and V ∈ C } for the left part. ΑΒ = { UV | U ∈ A, V ∈ B }, ΑC = { UV | U ∈ A, V ∈ c }, AB ∩ AC = { UV | U ∈ AB and AC, V ∈ AB and AC } for the right part. How can I ...
1
vote
1answer
52 views

Proof of an Infinite Binary Sequence

I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}* such that ww is a prefix of S. I need to prove that if ...
1
vote
4answers
77 views

Proving B* = B on a given set

I have the set: B = {x ∈ {0,1}* | there is an equal number of 0's and 1's in x} and therefore, B* = {e,01,10,0011,0101,0110,1100,1010,1001,....etc} I need to either prove or disprove that B*=B I ...
1
vote
0answers
51 views

Sum of long geometric progression [closed]

Finding sum of a geometric progression is simple when we just need to report the sum, but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me. I have a ...
2
votes
0answers
46 views

Can Pareto Optimality be compared to Nash Equilibrium?

Given a state $s$, and a value function $v^i$ that determines the expected payoff for the i-th agent in that state, can the two definitions below, one of Nash equilibrium and another of Pareto ...
1
vote
0answers
26 views

Proof that G is a Tree After DFS and BFS form the same tree T [closed]

Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth first search ...
1
vote
1answer
36 views

Prove Halting on all Inputs is not in RE simulation

I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
1
vote
0answers
183 views

Could you show the intractibility of SAT by showing that the number of variables contributing to an arbitrary unsatisfied clause is not constant? [closed]

Preface: This is not an attempted proof at P vs NP Starting with some CNF Boolean expression ϕ, by the rules of logical disjunction, a clause is only unsatisfied if each of the literals in it are ...
0
votes
1answer
41 views

Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem? [duplicate]

Why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem is nondeterministic polynomial time? Please note: this is not a question on how ...
0
votes
0answers
39 views

Correctness proof: induction on sequence of steps, need a stronger claim?

Im trying to prove the correctness of the construction proposed in this site answer: a two stack PDA that simulates a Turing Machine. By "correctness" i mean to prove more or less formally that we can ...
2
votes
2answers
39 views

Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$

How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ is decidable ? I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\}$ is not.
2
votes
4answers
68 views

Prooving by Pigeonhole principle

I've been given a question to solve: ...
1
vote
2answers
95 views

How to generate an instance for an NP_hard proof, where each element has two inputs?

I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
0
votes
0answers
16 views

How to prove that models of indirect and direct RAM machines are equivalent?

as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
0
votes
1answer
31 views

Is this a valid induction proof example ?

Learning induction proof now, found a "simple" example, which is a bit confusing to me (not sure if it is a valid example). If so, why the IH( suppose a root of rank k has at least $2^k$ vertices in ...
2
votes
1answer
42 views

Turing machine with semi infinite tape - Prove by construction

I'm studying constrained Turing Machines. There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 ...
1
vote
1answer
31 views

Trouble understanding this proof about the minimum number of states of a deterministic finite automaton

So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding ...
1
vote
3answers
39 views

Intuitive proof for a tree with n nodes, has n-1 edges

I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.
2
votes
1answer
36 views

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
1
vote
1answer
83 views

Proving problem NP-completeness [duplicate]

I am studying computational complexity and i am trying to solve this problem. We are given a (non-bipartite) complete graph: G = (V, W, E) where the vertices can be divided in two classes V and W ...
4
votes
2answers
159 views

Proving a value is the result of the execution of an algorithm

Assuming an algorithm $A$ known to both Alice and Bob. Alice runs the algorithm and gets a result $R$. How can Alice prove to Bob that $R$ is the result of the execution of $A$ and not some random ...
1
vote
1answer
31 views

Proof for Turing Machines being able to simulate any algorithm in the same time complexity

I have always read that Turing machines can simulate any algorithm, without changing the time complexity of the algorithm, and hence it is easier to study the Turing machine equivalent of the ...
1
vote
1answer
42 views

Proof By Contradiction - Hamiltonian Paths and Cycles

Was hoping if anyone had any way to prove the following claim using proof by contradiction Let $G = (V, E)$ be a simple graph with at least one vertex, and let $G'$ be the graph formed by adding a ...
0
votes
1answer
22 views

Showing $2^x$ is a lower bound

How do I show that $2^x - x^2 \in \Omega(2^x)$? Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$. I worked around a bit with ...
1
vote
0answers
30 views

How do we know that Icosoku always has solutions?

This is a continuation of a question I asked here. The puzzle Icosoku is now described by Wikipedia as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-...
1
vote
3answers
99 views

Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half ...
0
votes
1answer
17 views

There could not be an edge from u to v in a DAG, if w is before v in a topological order

I am trying to prove that given a DAG. There exists a valid topological ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post ...
2
votes
0answers
27 views

Challenging exercises for proof correctness [closed]

I would like to know where I can find challenging exercises that ask to prove the correctness of an algorithm. The invariant of most of the exercises I’ve found on the internet are quite easy (...
1
vote
1answer
89 views

lower bound proof with adversary argument

We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...
2
votes
1answer
55 views

How to reduce a problem?

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable. $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
3
votes
1answer
112 views

Undecidable problem intersection of two DCFL languages is DCFL?

We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
1
vote
0answers
45 views

How to prove that the predecessor of each node in Dijkstra form a tree?

Prove that the array prev[.] computed by Dijkstra’s algorithm, the edges (v, prev[v]) for all v ∈ V , form a tree In order to prove this I used induction. Lemma :...
2
votes
1answer
47 views

How to Apply Elementary Axioms from Kleene Star to an Inequality

Axioms For * \begin{align} 1 + aa^* &\leq a^* \\ 1 + a^*a &\leq a^* \\ b + ax &\leq x \to a^*b \leq x \\ b + xa &\leq x \to ba^* \leq x \\ \end{align} Elementary Results \begin{...
6
votes
3answers
2k views

Prove that A** = A*, where A is a language over Σ*

Let $\mathcal A$ be an arbitrary language over $\Sigma^*$ Proof. To prove, $\mathcal A^{**} = \mathcal A^* $ $\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \...
3
votes
1answer
39 views

Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle?

As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle. My attempt is that: So this graph would be an counter example ...
3
votes
1answer
133 views

Relating a proof to a Haskell program

I am trying to relate the following integer square root theorem $\forall x: \mathbb{N}, \exists y : \mathbb{N}((y^2 \leq x) \land (x < (y+1)^2))$ and its proof to its role as a specification of ...
5
votes
1answer
112 views

Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

It is a classic problem to simulate a fair coin with a biased one. According to Fair Coin (wiki), John von Neumann gave the following procedure: Toss the coin twice. If the results ...
0
votes
1answer
53 views

Does indirect diagonalization a relativize technique?

My main question is can with R.kanon , Fortnow ,... technique that shows lower bounds for SAT seperate P and NP ? Baker-Gill-Solovay showed that $P?=NP$ could not be solved with relativization. Does ...
3
votes
1answer
69 views

Removing arithmetic within recurrences

A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works. Say, for $T(n) = T(\lceil n/5 \rceil + 36) + n \log n$ ...
3
votes
1answer
51 views

How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?

How to prove that a string, s is made up of n > 1 subsequences occurring some arbitrary number of times using concatenation ...
1
vote
1answer
44 views

Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive

I'm stuck on this problem: Given $f:\mathbb{N} \rightarrow \mathbb{N}$ a partial recursive function that is also injective and total. Prove that the function $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$...
1
vote
1answer
82 views

Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is **not** recursively enumerable

So I tried to prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is not recursively enumerable in the following way: let's suppose that $g$ is the computable function that represents $D$ $$g(x) ...
1
vote
1answer
41 views

Prove that $L^r$ is context free without alphabet

I'm stuck with this problem: Given $L$ a CFL on the alphabet $\Sigma$. Prove that $L^r=\{x^r|x\in L\}$, where for each $a\in\Sigma$ and $y\in\Sigma^*$, $$\epsilon^r=\epsilon,$$ $$(ay)^r=y^ra,$$ is ...
3
votes
1answer
50 views

Why is the graph inside Graham Scan always planar

One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's ...
0
votes
1answer
74 views

Is Loop Invariant Proof a form of Induction?

As far as I see, what computer scientists refer to as loop invariant proofs are exact replicas of induction proof. Is it true? Can I state that loop invariant proof implies an induction? Is there a ...
1
vote
0answers
16 views

Strategy / Technique for Proving Equivalence between Multiple Program Forms

Wondering how to prove different compiled forms of a program to be "effectively the same" or "equivalent". For example, you can have a program represented as your normal nested function calls, or ...