… nearly 42 …

Main menu

Skip to primary content
Skip to secondary content
  • CSTheory
  • NPC Pills
  • YA(T) Open Problems
  • Games’n’Puzzles
  • About nearly42.org

Tag Archives: Post Correspondence Problem

Noodling with TCS: PCP variant

Posted on December 20, 2020 by admin
Reply

On my favourite TCS site cstheory.stackexchange.com I found a simple question about the Post Correspondence Problem:

If the upper and lower words of each domino must have different lengths, is the problem still undecidable? (we call this variant $PCP^{\neq}$).

The answer is yes, it remains undecidable …

Continue reading →
Posted in CSTheory | Tagged Post Correspondence Problem | Leave a reply

Recent Posts

  • Noodling with TCS: PCP variant
  • Cellular Automata variant
  • They exist but you cannot catch ’em
  • Box Shift Puzzle
  • A funny way to prove that the set of primes is not regular
  • Minimizing the COL4 to COL3 reduction
  • MiniZinc plays Dragster
  • The Power of One-State Turing Machines
  • Busy Beavers are (allmost) incompressible
  • NPC Pill #5: (P)izza =?= (NP)izza
  • Using Kolmogorov complexity to solve the Halting problem
  • Subway Shuffle is PSPACE-complete
  • NPC Pill #4: Square-Free Subset Product
  • NPC Pill #3: Pick 3 or Pick 2 … another NP-complete 3DM variant
  • YATOP #1: Are busy beavers lonely creatures?
  • NPC Pill #2: Minimal TSP Tour is coNP-Complete
  • NPC Pill #1: Single Overlap RX3C
  • Weapon-target assignment problem
  • New domain nearly42.org
  • The Crazy Frog Puzzle and Permutation Reconstruction from Differences
  • Complexity of the Hidden Polygon Puzzle
  • Hidato is NP-complete
  • Binary Puzzle is NP-complete
  • IcoSoKu solver
  • Three easy deletion games on paths

Recent Comments

  • Danny on IcoSoKu solver
  • Cole on Using Kolmogorov complexity to solve the Halting problem
  • Jaime Bonilla on Two bits are enough for a “hard” sum
  • peter taylor on IcoSoKu solver
  • Gary G on IcoSoKu solver

Archives

  • December 2020
  • October 2020
  • August 2020
  • December 2019
  • April 2019
  • March 2019
  • December 2018
  • January 2018
  • September 2017
  • November 2015
  • May 2015
  • April 2015
  • January 2015
  • August 2014
  • June 2014
  • March 2014
  • January 2014
  • December 2013
  • October 2013
  • September 2013
  • April 2013
  • March 2013
  • February 2013
  • January 2013
  • December 2012
  • November 2012
  • October 2012

Categories

  • CSTheory
  • Games'n'Puzzles
  • NPC Pills
  • Uncategorized
  • YA(T) Open Problems

Meta

  • Log in
  • Entries feed
  • Comments feed
  • WordPress.org
Copyright 2012-2025 fractalmuse.org