# 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.

638 questions
Filter by
Sorted by
Tagged with
36 views

### Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
683 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 ...
419 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 ...
331 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, ...
536 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 ...
308 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 ...
92 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 ...
65 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 ...
52 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 ...
558 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 ...
660 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 ...
193 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 ...
58 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 ...
57 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.
119 views

### Prooving by Pigeonhole principle

I've been given a question to solve: ...
122 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 (...
46 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 ...
687 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 ...
1k 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 ...
356 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.
396 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$ ...
205 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 ...
197 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 ...
259 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 ...
122 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 ...
52 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 ...
88 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-...
2k 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 ...
25 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 ...
61 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 (...
293 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 ...
92 views

46 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 that ...
225 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 ...
271 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 match, start over,...
88 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 ...
71 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$ ...
114 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 ...
187 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}$...
171 views

125 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 ...
947 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 ...
21 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 ...