https://blog.computationalcomplexity.org/2026/02/assigning-open-problems-in-class.html

Computational Complexity

Computational Complexity and other fun stuff in math and computer
science from Lance Fortnow and Bill Gasarch

Sunday, February 15, 2026

Assigning Open Problems in Class

I sometimes assign open problems as extra credit problems. Some
thoughts:

1) Do you tell the students the problems are open?

YES- it would be unfair for a student to work on something they
almost surely won't get.

NO- Some Open Problems are open because people are scared to work on
them. Having said that, I think P vs NP is beyond the one smart
person phase or even the if they don't know it's hard maybe they can
solve it phase.

NO- See Page 301 of this interview with George Dantzig where he talks
about his mistaking an open problem for a homework and ... solving
it.

CAVEAT---There are OPEN PROBLEMS!!! and there are open problems??? 
If I make up a problem, think about it for 30 minutes, and can't
solve it, it's open but might not be hard. See next point. 

 I tell the students:

This is a problem I made up but could not solve. It may be that I am
missing just one idea or combination of ideas so it is quite possible
you will solve it even though I could not. Of course, it could be
that it really is hard. 

A friend of mine who is not in academia thought that telling the
students that I came up with a problem I could not solve, but maybe
they can,  is a terrible idea. He said that if a student solves it,
they will think worse of me. I think he's clearly wrong.  If I am
enthused about their solution and give NO indication that I was close
to solving it (even if I was) then there is no way they would think
less of me.

Is there any reason why telling the students I could not solve it but
they might be able to is a bad idea? 

2) Should Extra Credit count towards the grade? (We ignore that there
are far more serious problems with grades with whatever  seems to
make them obsolete: Calculators, Cliff  notes,  Cheating,
Encyclopedias, Wikipedia, the Internet, ChatGPT, other AI, your
plastic pal who's fun to be with.) 

No- if they count towards the grade then they are not extra credit. 

I tell the students they DO NOT count for the grade but they DO count
for a letter I may write them.

What do you do? 

Posted by gasarch at 2:16 PM # #
Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

8 comments:

 1. [blank]
    Anonymous3:20 PM, February 15, 2026

    "Is there any reason why telling the students I could not solve
    it but they might be able to is a bad idea?"

    You are their teacher and they might feel you should have more
    abilities and skills than them since you are grading them.

    ReplyDelete
    Replies
     1. [David_2009]
        David Marcus3:38 PM, February 15, 2026

        As a teacher, I'd be happy if my students were better than
        me. I hope the students would be happy too, as long as I was
        helping them progress.

        Delete
        Replies
            Reply
        Reply
 2. [David_2009]
    David Marcus3:39 PM, February 15, 2026

    It is fine for extra credit to count for the grade as long as it
    can only increase the grade and the students could still get A's
    without doing the extra credit.

    ReplyDelete
    Replies
        Reply
 3. [holden-cur]
    Joshua Holden10:43 PM, February 15, 2026

    If it doesn't count towards the grade, it's not "extra credit".
    It's just extra.

    ReplyDelete
    Replies
        Reply
 4. [blogger_lo]
    Charles G2:55 PM, February 16, 2026

    You helped me at a rough time when I was going through a lot in
    my PhD by giving me an open problem and telling me it was open.

    ReplyDelete
    Replies
        Reply
 5. [blogger_lo]
    Josh Burdick4:52 PM, February 16, 2026

    If you come up with an "open problem", ask a bunch of people
    about it, and one or more of them solve it, I don't think you
    should be embarassed. (If it were me, I might be embarassed
    anyway -- but I don't think I should be. Unless, like, it turns
    out that it was an easy problem.)

    I think there's enough variety in how things might be proved, and
    luck (in terms of what methods a given person has seen), that
    it's hard to predict who can prove what. (Maybe something similar
    applies to AIs?)

    If I were a student, I'd prefer that open problems be marked as
    such. If a prof assigned a problem and said "I can't solve this",
    I would not think less of them if I happened to solve it. (See
    above re luck etc.)

    If "assigning a problem that you can't solve" is an issue:
    presumably you've thought about it enough to maybe have a partial
    approach? In that case, you could assign steps of that as
    sub-problems. (Assuming that you've worked out some of the
    steps.)

    ReplyDelete
    Replies
        Reply
 6. [blank]
    Leo8:24 PM, February 17, 2026

    Your letter of recommendation is important, but the student's
    grades are also important; the two are not mutually exclusive.
    Both count.

    ReplyDelete
    Replies
        Reply
 7. [blank]
    Anonymous4:56 PM, February 18, 2026

    I think you should include it in their grade. A grade is meant to
    indicate mastery over the material. Are you really going to write
    that letter for someone who got a D? Or give them a D if they
    solve an unsolved problem? Is that showing their true mastery of
    the material?

    ReplyDelete
    Replies
        Reply

Add comment
Load more...

 

Newer Post Older Post Home
Subscribe to: Post Comments (Atom)

Books

[9780691175]

Commissions earned from Amazon Links

Mastodon Feed

Blog Links

  * Bill's Home Page
  * Lance's Home Page
  * Favorite Theorems
  * Foundations of Complexity Lessons
  * Graduate Student Guide
  * ChatPNP
  * Ask Questions to the Blog
  * CACM P v NP Survey (2009)
  * CACM Fifty Years of P vs. NP (2022)
  * CACM Conference Viewpoint
  * Podcasts
  * Videos
  * Posts Feed
  * Comments Feed

Popular Posts

  * What to do about students using ChatGPT to do their homework?
  * The 17x17 challenge. Worth $289.00. This is not a joke.
  * FOCS Accepts and a Movie
  * Assigning Open Problems in Class
  * The Future of Mathematics and Mathematicians
  * The End
  * Why did 1+1=2 take Russell and Whitehead 300 pages?
  * Before the ChatGPT-HW debate there were other ``If students use X
    to do their HW'' debates
  * Name My Book
  * Intelligent questions about the alleged P NE NP proof

Complexity Links

  * Complexity Conference
  * SIGACT
  * Theory Announcements
  * Theory Stack Exchange
  * Complexity Zoo
  * Complexity on arXiv
  * Electronic Colloquium on Computational Complexity

Blog Archive

  * V  2026 (15)
      + V  February (6)
          o Joe Halpern (1953-2026)
          o Assigning Open Problems in Class
          o The Future of Mathematics and Mathematicians
          o I used to think historians in the future will have...
          o Sampling the Oxford CS Library
          o Before the ChatGPT-HW debate there were other ``If...
      + >  January (9)

  * >  2025 (98)
      + >  December (6)
      + >  November (8)
      + >  October (9)
      + >  September (8)
      + >  August (8)
      + >  July (9)
      + >  June (9)
      + >  May (8)
      + >  April (8)
      + >  March (9)
      + >  February (6)
      + >  January (10)

  * >  2024 (102)
      + >  December (7)
      + >  November (7)
      + >  October (9)
      + >  September (9)
      + >  August (7)
      + >  July (8)
      + >  June (11)
      + >  May (9)
      + >  April (9)
      + >  March (8)
      + >  February (8)
      + >  January (10)

  * >  2023 (92)
      + >  December (6)
      + >  November (8)
      + >  October (8)
      + >  September (7)
      + >  August (8)
      + >  July (9)
      + >  June (6)
      + >  May (9)
      + >  April (7)
      + >  March (8)
      + >  February (8)
      + >  January (8)

  * >  2022 (77)
      + >  December (7)
      + >  November (7)
      + >  October (9)
      + >  September (6)
      + >  August (7)
      + >  July (6)
      + >  June (5)
      + >  May (6)
      + >  April (5)
      + >  March (6)
      + >  February (7)
      + >  January (6)

  * >  2021 (89)
      + >  December (6)
      + >  November (7)
      + >  October (8)
      + >  September (8)
      + >  August (9)
      + >  July (7)
      + >  June (7)
      + >  May (8)
      + >  April (8)
      + >  March (7)
      + >  February (6)
      + >  January (8)

  * >  2020 (76)
      + >  December (8)
      + >  November (7)
      + >  October (7)
      + >  September (7)
      + >  August (6)
      + >  July (6)
      + >  June (6)
      + >  May (7)
      + >  April (7)
      + >  March (9)
      + >  February (1)
      + >  January (5)

  * >  2019 (84)
      + >  December (4)
      + >  November (3)
      + >  October (8)
      + >  September (7)
      + >  August (2)
      + >  July (8)
      + >  June (9)
      + >  May (9)
      + >  April (9)
      + >  March (8)
      + >  February (8)
      + >  January (9)

  * >  2018 (100)
      + >  December (7)
      + >  November (8)
      + >  October (10)
      + >  September (8)
      + >  August (9)
      + >  July (8)
      + >  June (8)
      + >  May (9)
      + >  April (9)
      + >  March (8)
      + >  February (8)
      + >  January (8)

  * >  2017 (101)
      + >  December (7)
      + >  November (8)
      + >  October (9)
      + >  September (8)
      + >  August (8)
      + >  July (9)
      + >  June (9)
      + >  May (9)
      + >  April (9)
      + >  March (8)
      + >  February (8)
      + >  January (9)

  * >  2016 (101)
      + >  December (9)
      + >  November (8)
      + >  October (9)
      + >  September (6)
      + >  August (8)
      + >  July (7)
      + >  June (10)
      + >  May (9)
      + >  April (10)
      + >  March (8)
      + >  February (9)
      + >  January (8)

  * >  2015 (103)
      + >  December (7)
      + >  November (9)
      + >  October (9)
      + >  September (8)
      + >  August (9)
      + >  July (9)
      + >  June (10)
      + >  May (8)
      + >  April (9)
      + >  March (9)
      + >  February (8)
      + >  January (8)

  * >  2014 (111)
      + >  December (8)
      + >  November (8)
      + >  October (10)
      + >  September (11)
      + >  August (9)
      + >  July (9)
      + >  June (11)
      + >  May (10)
      + >  April (10)
      + >  March (8)
      + >  February (8)
      + >  January (9)

  * >  2013 (108)
      + >  December (9)
      + >  November (8)
      + >  October (8)
      + >  September (11)
      + >  August (9)
      + >  July (9)
      + >  June (8)
      + >  May (9)
      + >  April (10)
      + >  March (9)
      + >  February (9)
      + >  January (9)

  * >  2012 (132)
      + >  December (7)
      + >  November (9)
      + >  October (12)
      + >  September (10)
      + >  August (10)
      + >  July (9)
      + >  June (10)
      + >  May (12)
      + >  April (12)
      + >  March (15)
      + >  February (14)
      + >  January (12)

  * >  2011 (134)
      + >  December (10)
      + >  November (10)
      + >  October (12)
      + >  September (13)
      + >  August (10)
      + >  July (10)
      + >  June (14)
      + >  May (11)
      + >  April (12)
      + >  March (12)
      + >  February (11)
      + >  January (9)

  * >  2010 (191)
      + >  December (8)
      + >  November (12)
      + >  October (15)
      + >  September (14)
      + >  August (18)
      + >  July (15)
      + >  June (17)
      + >  May (20)
      + >  April (22)
      + >  March (20)
      + >  February (15)
      + >  January (15)

  * >  2009 (249)
      + >  December (16)
      + >  November (19)
      + >  October (23)
      + >  September (21)
      + >  August (21)
      + >  July (23)
      + >  June (23)
      + >  May (22)
      + >  April (21)
      + >  March (22)
      + >  February (20)
      + >  January (18)

  * >  2008 (253)
      + >  December (19)
      + >  November (18)
      + >  October (27)
      + >  September (21)
      + >  August (19)
      + >  July (22)
      + >  June (23)
      + >  May (23)
      + >  April (22)
      + >  March (20)
      + >  February (21)
      + >  January (18)

  * >  2007 (159)
      + >  December (10)
      + >  November (15)
      + >  October (18)
      + >  September (10)
      + >  August (13)
      + >  July (11)
      + >  June (8)
      + >  May (8)
      + >  April (7)
      + >  March (16)
      + >  February (20)
      + >  January (23)

  * >  2006 (238)
      + >  December (18)
      + >  November (22)
      + >  October (22)
      + >  September (19)
      + >  August (24)
      + >  July (18)
      + >  June (18)
      + >  May (18)
      + >  April (18)
      + >  March (21)
      + >  February (20)
      + >  January (20)

  * >  2005 (237)
      + >  December (18)
      + >  November (20)
      + >  October (24)
      + >  September (19)
      + >  August (22)
      + >  July (17)
      + >  June (19)
      + >  May (21)
      + >  April (19)
      + >  March (17)
      + >  February (17)
      + >  January (24)

  * >  2004 (200)
      + >  December (18)
      + >  November (16)
      + >  October (19)
      + >  September (15)
      + >  August (16)
      + >  July (15)
      + >  June (18)
      + >  May (13)
      + >  April (13)
      + >  March (17)
      + >  February (16)
      + >  January (24)

  * >  2003 (149)
      + >  December (13)
      + >  November (12)
      + >  October (15)
      + >  September (11)
      + >  August (7)
      + >  July (11)
      + >  June (13)
      + >  May (10)
      + >  April (15)
      + >  March (15)
      + >  February (11)
      + >  January (16)

  * >  2002 (76)
      + >  December (20)
      + >  November (17)
      + >  October (15)
      + >  September (18)
      + >  August (6)

Blog Roll

  * 
    What's new
    Six Math Essentials
    2 days ago
  * 
    Daniel Lemire's blog
    How bad can Python stop-the-world pauses get?
    3 days ago
  * 
    Shtetl-Optimized
    On reducing the cost of breaking RSA-2048 to 100,000 physical
    qubits
    3 days ago
  * 
    11011110
    Linkage
    3 days ago
  * 
    Healthy Algorithms
    The Douglass-Truth Library Has How Unlikely a Name? A Little
    Simulation in Python
    1 week ago
  * 
    Theory Matters
    Trevisan Award for Expository Work
    1 week ago
  * 
    Windows On Theory
    Trevisan Award for Expository Work
    1 week ago
  * 
    Thoughts
    Lust for life
    1 week ago
  * 
    Combinatorics and more
    Updates and Plans V: From Boise to Tel Aviv, Ceasefire, My 70th
    Birthday, Nostalgia, Problems, Outrageous Conjectures, Quantum,
    and AI
    2 weeks ago
  * 
    GovAffairs
    CRA and ACM's USTPC Respond to NSF's Request for Community Input
    about its Draft Strategic Plan
    2 weeks ago
  * 
    Process Algebra Diary
    EATCS Distinguished Dissertation Award 2025 -- Call for
    Nominations
    4 weeks ago
  * 
    Theory Dish
    STOC 2026 Call for Workshops
    4 weeks ago
  * 
    Turing's Invisible Hand
    SIGecom Doctoral Dissertation Award
    1 month ago
  * 
    Mathematical Enchantments
    Is Matrix Multiplication Ugly?
    2 months ago
  * 
    The Intelligence Loop
    How Machines Learn to Write
    4 months ago
  * 
    Opinions of Doron Zeilberger

Show 10 Show All
Creative Commons License
Computational Complexity Weblog by Lance Fortnow and William Gasarch
is licensed under a Creative Commons Attribution-NonCommercial 4.0
International License. Additional permissions can be requested.
 
Powered by Blogger.